[알고스팟]게임판 덮기(BOARDCOVER)

문제

H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다. 위 그림은 한 게임판과 이를 덮는 방법을 보여줍니다.

게임판이 주어질 때 이를 덮는 방법의 수를 계산하는 프로그램을 작성하세요.

 

입력

력의 첫 줄에는 테스트 케이스의 수 C (C <= 30) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 2개의 정수 H, W (1 <= H,W <= 20) 가 주어집니다. 다음 H 줄에 각 W 글자로 게임판의 모양이 주어집니다. # 은 검은 칸, . 는 흰 칸을 나타냅니다. 입력에 주어지는 게임판에 있는 흰 칸의 수는 50 을 넘지 않습니다.

 

출력

한 줄에 하나씩 흰 칸을 모두 덮는 방법의 수를 출력합니다.

 

풀이

 

종만북 완전탐색 2번째 문제이다

 

1. L자 블록은 3칸으로 이루어져있다. 3칸씩 빈칸을 채우는 것을 최소부분으로 생각한다. 그리고 빈칸이 3의 배수가 아니라면 L자 블록으로 채울 수 있는 방법은 0이다.

 

2. 맨 왼쪽 상단부터 차례대로 조사하여 빈칸이라면 L자 블록으로 채우도록 한다. 그러면 마구잡이로 채워지는 것을 방지할 수 있다. 

 

3. 2번 제약사항을 추가하였기 때문에 맨 왼쪽 상단부터 L자 블록으로 덮을 수 있는 방법은 최대 4가지 경우밖에 없다.

 

4. 보드 영역을 벗어나거나 L자 블록이 이미 블록이 있는 부분을 또 덮는경우를 제외하고 재귀함수를 돌면서답을 찾으면 된다.

 

소스코드

#include <iostream>
#include <vector>
 
using namespace std;
 
const int coverType[4][3][2] = 
{
    {{0,0},{1,0},{0,1}},
    {{0,0},{1,0},{1,1}},
    {{0,0},{0,1},{1,1}},
    {{0,0},{0,1},{-1,1}}
};
 
bool set(vector< vector<int> > &board, int x, int y, int type, int delta)
{
    bool result = true;
    
    for (int i = 0; i < 3; ++i)
    {
        int nx = x + coverType[type][i][0];
        int ny = y + coverType[type][i][1];
        if (nx < 0 || ny < 0 || nx >= board[0].size() || ny >= board.size())
            result = false;
        else if ((board[ny][nx] += delta) > 1)
            result = false;
    }
 
    return result;
}
 
int cover(vector< vector<int> > &board)
{
    int startX = -1, startY = -1;
    for (int i = 0; i < board.size(); ++i)
    {
        for (int j = 0; j < board[0].size(); ++j)
        {
            if (board[i][j] == 0)
            {
                startX = j;
                startY = i;
                break;
            }
        }
        if (startX != -1) break;
    }
 
    if (startX == -1) return 1;
 
    int ret = 0;
    for (int type = 0; type < 4; ++type)
    {
        if (set(board, startX, startY, type, 1))
            ret += cover(board);
        set(board, startX, startY, type, -1);
    }
    return ret;
}
 
int main()
{
    cin.sync_with_stdio(false);
    cin.tie(false);
    cout.tie(false);
 
    int testCase;
    cin >> testCase;
    
    for (int i = 0; i < testCase; ++i)
    {
        int h, w, cnt = 0;
        cin >> h >> w;
        vector< vector<int> > board(h);
        for (int j = 0; j < h; ++j)
        {
            for (int k = 0; k < w; ++k)
            {
                char input;
                cin >> input;
                if (input == '#') board[j].push_back(1);
                else 
                {
                    board[j].push_back(0);
                    cnt++;
                }
            }
        }
        if (cnt % 3 == 0)
            cout << cover(board) << endl;
        else
            cout << 0 << endl;
    }
}

 

링크

https://www.algospot.com/judge/problem/read/BOARDCOVER