종만북 p.161 게임판 덮기(brute force)

#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
const int coverType[4][3][2] = {
    {{0, 0}, {1, 0}, {0, 1}},
    {{0, 0}, {0, 1}, {1, 1}},
    {{0, 0}, {1, 0}, {1, 1}},
    {{0, 0}, {1, 0}, {1, -1}}};
 
bool set(vector<vector<int>> &board, int y, int x, int type, int delta)
{
    bool ok = true;
    for (int i = 0; i < 3; i++)
    {
        const int ny = y + coverType[type][i][0];
        const int nx = x + coverType[type][i][1];
        if (ny < 0 || ny >= board.size() || nx < 0 || nx >= board[0].size())
            ok = false;
        else if ((board[ny][nx] += delta) > 1)
            ok = false;
    }
    return ok;
}
 
int cover(vector<vector<int>> &board)
{
    int y = -1, x = -1;
    for (int i = 0; i < board.size(); i++)
    {
        for (int j = 0; j < board[i].size(); j++)
        {
            if (!board[i][j])
            {
                y = i;
                x = j;
                break;
            }
        }
        if (y != -1)
            break;
    }
    if (y == -1)
        return 1;
    int ret = 0;
    for (int type = 0; type < 4; type++)
    {
        if (set(board, y, x, type, 1))
            ret += cover(board);
        set(board, y, x, type, -1);
    }
    return ret;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int num;
    cin >> num;
 
    while (num--)
    {
        int row, column;
        cin >> row >> column;
        vector<vector<int>> board(row, vector<int>(column, 0));
        for (int i = 0; i < row; i++)
        {
            string s;
            cin >> s;
            for (int j = 0; j < s.size(); j++)
            {
                if (s[j] == '#')
                    board[i][j] = 1;
                else
                    board[i][j] = 0;
            }
        }
        cout << cover(board) << "\n";
    }
}
 

항상 brute force를 풀 때 중요한 것이 중복을 피하는 문제인 것 같다. 이 문제에서는 항상 맨 윗줄의 맨 왼쪽을 기준으로 판단함으로써 중복을 피하고 있다. 솔직히 이 문제도 혼자서 풀었다면 이런 스킬은 생각지도 못했을 것 같다.