[C++] 알고스팟 - BOARDCOVER

문제 링크

algospot.com :: BOARDCOVER

 

풀이 )

  먼저 입력받은 '.'의 개수를 세서 3으로 나누어떨어지지 않는 경우 '0'을 출력하고 종료한다.

  '.'의 개수를 3으로 나누어 보드에 들어가는 총 블록의 수를 세고, DFS로 보드에 블록을 채워준다.

 

  DFS 함수 내에서는 기저사례로 남은 블록 수가 0일 때 1을 반환하게 한다.

  board에서 위에서부터 보면서 첫 '.'을 찾고, 그 위치에서 4종류의 블록을 넣어보면서 다음 블록을 채워 넣는다.

 

#include <iostream>
#include <string>

using namespace std;

int block[4][3][2] = {
    {{0, 0}, {1, 0}, {1, 1}},
    {{0, 0}, {0, 1}, {1, 1}},
    {{0, 0}, {1, 0}, {0, 1}},
    {{0, 0}, {1, 0}, {1, -1}}
};

int h, w;

int dfs(string board[], int numBlock){
    if(!numBlock)
        return 1;

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

    int ret = 0;
    for(int i = 0; i < 4; ++i){
        bool flag = 0;
        for(int j = 0; j < 3; ++j){
            int nx = x+block[i][j][0];
            int ny = y+block[i][j][1];
            if(nx < 0 || nx >= h || ny < 0 || ny >= w || board[nx][ny] == '#'){
                flag = true;
                break;
            }
        }
        if(flag)
            continue;

        for(int j = 0; j < 3; ++j){
            int nx = x+block[i][j][0];
            int ny = y+block[i][j][1];
            board[nx][ny] = '#';
        }
        ret += dfs(board, numBlock-1);
        for(int j = 0; j < 3; ++j){
            int nx = x+block[i][j][0];
            int ny = y+block[i][j][1];
            board[nx][ny] = '.';
        }
    }
    return ret;
}

int main(void){
    int c;
    cin >> c;
    while(c--){
        cin >> h >> w;
        string* board = new string[h];
        int numBlock = 0;
        for(int i = 0; i < h; ++i){
            cin >> board[i];
            for(int j = 0; j < w; ++j){
                if(board[i][j] == '.')
                    numBlock++;
            }
        }
        if(numBlock%3){
            cout << 0 << '\n';
            continue;
        }
        numBlock/=3;

        cout << dfs(board, numBlock) << '\n';
    }
}