게임판 덮기(BOARDCOVER) 정답 코드

난이도 ★★★★☆

문제를 보시려면 여기를 클릭

힌트

재귀로 탐색하면 편리하다.  → ① 왼쪽 위 점을 기준으로 잡고 하면 좋다. 그렇게 되면 가능한 경우가 4가지만 나온다.  → ② 탐색 중에 덮었으면(cover) 꼭 다시 벗겨줘야(uncover) 한다.

이하는 코드입니다.

#include <stdio.h>
#include <vector>
 
#define WALL 1
#define EMPTY 0
 
#pragma warning(disable:4996)
 
using namespace std;
 
int H, W;
vector<vector<int>> board;
int coverCount;
 
void getCount(int y, int x) {
    // get left-top
    int i, j;
    bool found = false;
    for (i = y; i < H; i++) {
        if (i == y) {
            j = x;
        }
        else {
            j = 0;
        }
        for (; j < W; j++) {
            if (board[i][j] == EMPTY) {
                found = true;
                break;
            }
        }
 
        if (found) {
            break;
        }
    }
 
    // there is no EMPTY → case found
    if (!found) {
        coverCount++;
        return;
    }
 
    // last row → impossible case
    if (i > H - 2) {
        return;
    }
 
    // last column → only 」case could be possible
    if (j > W - 2) {
        // 」
        if ((board[i + 1][j - 1] == EMPTY) && (board[i + 1][j] == EMPTY)) {
            // cover
            board[i][j]++;
            board[i + 1][j - 1]++;
            board[i + 1][j]++;
 
            getCount(i, j);
 
            // uncover
            board[i][j]--;
            board[i + 1][j - 1]--;
            board[i + 1][j]--;
        }
 
        return;
    }
 
    // neither last row nor last column → all cases could be possible
    else {
        // ㄱ
        if ((board[i][j + 1] == EMPTY) && (board[i + 1][j + 1] == EMPTY)) {
            // cover
            board[i][j]++;
            board[i][j + 1]++;
            board[i + 1][j + 1]++;
 
            getCount(i, j);
 
            // uncover
            board[i][j]--;
            board[i][j + 1]--;
            board[i + 1][j + 1]--;
        }
 
        // 「
        if ((board[i][j + 1] == EMPTY) && (board[i + 1][j] == EMPTY)) {
            // cover
            board[i][j]++;
            board[i][j + 1]++;
            board[i + 1][j]++;
 
            getCount(i, j);
 
            // uncover
            board[i][j]--;
            board[i][j + 1]--;
            board[i + 1][j]--;
        }
 
        // 」
        if ((board[i + 1][j - 1] == EMPTY) && (board[i + 1][j] == EMPTY)) {
            // cover
            board[i][j]++;
            board[i + 1][j - 1]++;
            board[i + 1][j]++;
 
            getCount(i, j);
 
            // uncover
            board[i][j]--;
            board[i + 1][j - 1]--;
            board[i + 1][j]--;
        }
 
        // ㄴ
        if ((board[i + 1][j] == EMPTY) && (board[i + 1][j + 1] == EMPTY)) {
            // cover
            board[i][j]++;
            board[i + 1][j]++;
            board[i + 1][j + 1]++;
 
            getCount(i, j);
 
            // uncover
            board[i][j]--;
            board[i + 1][j]--;
            board[i + 1][j + 1]--;
        }
    }
}
 
int main() {
    int C;
    scanf("%d\n", &C);
 
    while (C-- > 0) {
        scanf("%d %d\n", &H, &W);
 
        // get board
        for (int i = 0; i < H; i++) {
            vector<int> line;
 
            for (int j = 0; j < W; j++) {
                char c;
                scanf("%c", &c);
 
                if (c == '.') {
                    line.push_back(EMPTY);
                }
                else {
                    line.push_back(WALL);
                }
            }
            board.push_back(line);
 
            // remove '\n'
            getchar();
        }
 
        // solve and print
        coverCount = 0;
        getCount(0, 0);
        printf("%d\n", coverCount);
 
        // reset
        if (C > 0) {
            board.clear();
        }
    }
 
    return 0;
}