백준 3967번 매직 스타 C++

https://www.acmicpc.net/problem/3967

3967번: 매직 스타

 

백트래킹

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int cnt = 0;
vector<bool> used(12, false);
vector<int> _fill;
vector<pair<int, int>> pos(12);
vector<vector<char>> board(5, vector<char>(9));

void BT(int idx, int currCnt) {
    if (currCnt == cnt) {
        int sum1, sum2, sum3, sum4, sum5, sum6;
        sum1 = board[0][4] + board[1][3] + board[2][2] + board[3][1];
        sum2 = board[0][4] + board[1][5] + board[2][6] + board[3][7];
        sum3 = board[3][1] + board[3][3] + board[3][5] + board[3][7];
        sum4 = board[1][1] + board[1][3] + board[1][5] + board[1][7];
        sum5 = board[1][1] + board[2][2] + board[3][3] + board[4][4];
        sum6 = board[1][7] + board[2][6] + board[3][5] + board[4][4];
        bool ans = true;
        if (sum1 != sum2) ans = false;
        if (sum2 != sum3) ans = false;
        if (sum3 != sum4) ans = false;
        if (sum4 != sum5) ans = false;
        if (sum5 != sum6) ans = false;
        if (ans) {
            for (auto a : board) {
                for (auto b : a) {
                    cout << b;
                }
                cout << "\n";
            }
            exit(0);
        }
        return;
    }
    for (int i = 0; i < 12; i++) {
        if (used[i]) continue;
        used[i] = true;
        board[pos[_fill[idx]].first][pos[_fill[idx]].second] = i + 'A';
        BT(idx + 1, currCnt + 1);
        used[i] = false;
        board[pos[_fill[idx]].first][pos[_fill[idx]].second] = 'x';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int idx = 0;
    for (int i = 0; i < 5; i++) {
        string str;
        cin >> str;
        for (int j = 0; j < str.length(); j++) {
            board[i][j] = str[j];
            if (board[i][j] == '.') continue;
            if (board[i][j] == 'x') {
                _fill.push_back(idx);
                cnt++;
            }
            else {
                used[str[j] - 'A'] = true;
            }
            pos[idx++] = { i,j };
        }
    }
    BT(0,0);
}