BOARDCOVER

문제 링크

BOARDCOVER

문제 풀이

왼쪽 위에서부터 가능한 블록의 모양을 덮고 재귀 호출로 남은 빈칸을 채운다. 이때, 빈칸의 수가 3의 배수가 아닐시 답이 없는 경우니 예외 처리한다.

구현

#include <iostream>
#include <string>
using namespace std;

int TC, H, W;
string board[20];

int blockType[4][3][2] = {
    { {0, 0}, {1, 0}, {0, 1} },// ㄱ y축 대칭
    { {0, 0}, {0, 1}, {1, 1} },// ㄱ
    { {0, 0}, {1, 0}, {1, 1} },// ㄴ
    { {0, 0}, {1, 0}, {1,-1} } // ㄴ y축 대칭
};

bool isfill(int y, int x, int type) {
    for (int i = 0; i < 3; ++i) {
        int ty = y + blockType[type][i][0];
        int tx = x + blockType[type][i][1];
        if (ty < 0 || ty >= H || tx < 0 || tx >= W) return false;
        else if (board[ty][tx] == '#') return false;
    }
    return true;
}

void set(int y, int x, int type, char block) {
    for (int i = 0; i < 3; ++i) {
        int ty = y + blockType[type][i][0];
        int tx = x + blockType[type][i][1];
        board[ty][tx] = block;
    }
}

int solve() {
    int y = -1, x = -1;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (board[i][j] == '.') {
                y = i; x = j; break;
            }
        }
        if (y != -1) break;
    }
    if (y == -1) return 1;

    int ret = 0;
    for (int i = 0; i < 4; ++i) {
        if (isfill(y, x, i)) {
            set(y, x, i, '#');
            ret += solve();
            set(y, x, i, '.');
        }
    }
    return ret;
}

int main() {
    cin >> TC;
    while (TC--) {
        int ch = 0;
        cin >> H >> W;
        for (int i = 0; i < H; ++i) {
            cin >> board[i];
            for (int j = 0; j < W; ++j)
                if (board[i][j] == '.')
                    ++ch;
        }
        if (ch % 3 == 0) cout << solve() << "\n";
        else cout << 0 << "\n";
    }
    return 0;
}