Judge - 1235 : Please In My Frontyard! C++

출처 : https://judge.koreatech.ac.kr/problem.php?id=1235

 

스도쿠 문제와 거의 똑같다. 백트래킹을 이용해서 풀었다.

 

#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;

const int SIZE = 9;

char PIMFYs[SIZE] = { 'A','B', 'C', 'D', 'E', 'F', 'G', 'H', 'I' };

int GetBoxNum(int row, int col) {
    if (row >= 0 && row <= 2) {
        if (col >= 0 && col <= 2)
            return 0;
        if (col >= 3 && col <= 5)
            return 1;
        return 2;
    }
    if (row >= 3 && row <= 5) {
        if (col >= 0 && col <= 2)
            return 3;
        if (col >= 3 && col <= 5)
            return 4;
        return 5;
    }
    if (col >= 0 && col <= 2)
        return 6;
    if (col >= 3 && col <= 5)
        return 7;
    return 8;
}

vector<vector<char>> board(SIZE, vector<char>(SIZE));
vector<vector<bool>> found_Row(SIZE, vector<bool>(SIZE, false));
vector<vector<bool>> found_Col(SIZE, vector<bool>(SIZE, false));
vector<vector<bool>> found_Box(SIZE, vector<bool>(SIZE, false));

void BT(int loc) {
    if (loc >= SIZE * SIZE) {
        for (auto a : board) {
            for (auto b : a) {
                cout << b << " ";
            }
            cout << "\n";
        }
        return;
    }

    int row = loc / SIZE;
    int col = loc % SIZE;

    if (board[row][col] == '.') {
        for (int i = 0; i < 9; i++) {
            char pimfy = PIMFYs[i];
            if (found_Row[row][pimfy - 'A']) continue;
            if (found_Col[col][pimfy - 'A']) continue;
            if (found_Box[GetBoxNum(row, col)][pimfy - 'A']) continue;

            found_Row[row][pimfy - 'A'] = true;
            found_Col[col][pimfy - 'A'] = true;
            found_Box[GetBoxNum(row, col)][pimfy - 'A'] = true;
            board[row][col] = pimfy;
            BT(loc + 1);
            found_Row[row][pimfy - 'A'] = false;
            found_Col[col][pimfy - 'A'] = false;
            found_Box[GetBoxNum(row, col)][pimfy - 'A'] = false;
            board[row][col] = '.';
        }
    }
    else {
        BT(loc + 1);
    }
}

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

    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            cin >> board[i][j];
            if (board[i][j] == '.')
                continue;
            found_Row[i][board[i][j] - 'A'] = true;
            found_Col[j][board[i][j] - 'A'] = true;
            found_Box[GetBoxNum(i, j)][board[i][j] - 'A'] = true;
        }
    }
    BT(0);
}