6장 무식하게 풀기 2

6.5 문제: 게임판 덮기 (문제ID: BOARDCOVER, 난이도: 하)

문제 자세히 보기

#include <iostream>

using namespace std;

bool board[20][20];      // board[H][W]
int dx[4][2] = { {0, 1}, {1, 1}, {0, 1}, {0, -1} };
int dy[4][2] = { {1, 1}, {0, 1}, {1, 0}, {1, 1} };

int dfs(int H, int W) {
    int cur = -1;
    int x, y;
    for (cur = 0; cur < H * W; ++cur) {
        y = cur / W;
        x = cur % W;
        if (board[y][x]) {
            break;
        }
    }
    if (cur == H * W) return 1;

    int cases = 0;
    int x1, x2, y1, y2;
    for (int i = 0; i < 4; ++i) {
        x1 = x + dx[i][0];
        y1 = y + dy[i][0];
        x2 = x + dx[i][1];
        y2 = y + dy[i][1];

        if (x1 >= W) continue;
        if (x2 < 0 || x2 >= W) continue;
        if (y1 >= H) continue;
        if (y2 >= H) continue;

        if (board[y1][x1] && board[y2][x2]) {
            board[y][x] = board[y1][x1] = board[y2][x2] = false;
            cases += dfs(H, W);
            board[y][x] = board[y1][x1] = board[y2][x2] = true;
        }
        
    }

    return cases;
}

int main() {
    int C;
    cin >> C;
    while (C--) {
        int cnt = 0;
        int H, W;
        cin >> H >> W;

        char ch;
        for (int i = 0; i < H * W; ++i) {
            cin >> ch;
            if (ch == '.') {
                board[i / W][i % W] = true;
                cnt++;
            }   
            else if (ch == '#') 
                board[i / W][i % W] = false;
        }

        if (cnt % 3) 
            cout << 0 << endl;
        else 
            cout << dfs(H, W) << endl;
        
    }

    return 0;
}

Back to top ↑