[ALGOSPOT] BOARDCOVER

출처 : algospot.com/judge/problem/read/BOARDCOVER

algospot.com :: BOARDCOVER

문제

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

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

 

입력

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

 

출력

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

 

<아이디어>

'.'인 모든 부분을 vector에 넣어 'L'자 모양을 하나씩 넣어가며 완전탐색

 

<구현>

vector<pair<int, int>> 에 '.'인 모든 부분의 좌표를 넣습니다. -> 앞에서부터 탐색하여 넣기때문에 굳이 정렬하지 않아도 됩니다.

'#'인 부분은 어짜피 채워넣을 수 없기 때문에 true한다.

vector<pair<int, int>>에 들어있는 좌표들이 모두 채워져야하며, 3으로 나누어 떨어져야 가능하다.

모든 '.'인부분이 채워져야하므로 채우지않고 넘어가는 경우를 없애기 위해 좌측 맨 위를 기준으로 채울 수 있는 4가지 경우의 수로 나눈다.

const int dy[4][2] = {{0, 1}, {1, 1}, {0, 1}, {1, 1}};
const int dx[4][2] = {{1, 1}, {0, 1}, {1, 0}, {-1, 0}};

범위체크 및 중복체크를 마치고 체크하면서 재귀적으로 진입한다.

남은 '.'의 수가 0이거나(return 1), 모든 '.'인 부분을 방문(return 0)하면 return 한다.

 

 

<실수한 부분>

좌측 맨 위를 기준으로 채울 수 있는 4가지를 생각했어야 중복을 줄이고 무한루프에 빠지지 않는데, dy, dx 배열을 만들기 쉽다고 아래와 같이 무조건 모서리 부분을 기준으로 탐색을 했다.

 

위와 같이 탐색을 하면 좌측 위가 항상 채워진다는 보장없이 빈칸인 채로 두고 재귀를 진입해야해서 굉장히 비효율적으로 탐색해야 한다. -> 무조건 시간초과난다.

 

이런 실수는 순열을 출력한다고 했을 때, 사전순으로 완전탐색 하지 않고 아무거나 하는 것과 같다.

 

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int h, w;
bool check[22][22];
const int dy[4][2] = {{0, 1}, {1, 1}, {0, 1}, {1, 1}};
const int dx[4][2] = {{1, 1}, {0, 1}, {1, 0}, {-1, 0}};
 
lld bt(int k, int rest, vector<pair<int, int>>& v)
{
    if(rest==0) return 1LL;
    else if(k>=v.size()) return 0LL;
    int y = v[k].first, x = v[k].second;
    if(check[y][x]) return bt(k+1, rest, v);
    lld res = 0LL;
    check[y][x] = true;
    for(int i=0;i<4;i++)
    {
        int y1 = y+dy[i][0], y2 = y+dy[i][1];
        int x1 = x+dx[i][0], x2 = x+dx[i][1];
        if(y1>=h||y2>=h||x1>=w||x2>=w) continue;
        else if(y1<0||y2<0||x1<0||x2<0) continue;
        else if(check[y1][x1]||check[y2][x2]) continue;
        check[y1][x1] = check[y2][x2] = true;
        res += bt(k+1, rest-3, v);
        check[y1][x1] = check[y2][x2] = false;
    }
    check[y][x] = false;
    return res;
}
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc;
    cin>>tc;
    while(tc--)
    {
        cin>>h>>w;
        vector<string> mp(h);
        memset(check, false, sizeof(check));
        vector<pair<int, int>> v;
        for(int i=0;i<h;i++)
            cin>>mp[i];
        int rest = 0;
        for(int i=0;i<h;i++)
        {
            for(int j=0;j<w;j++)
            {
                if(mp[i][j]=='#') check[i][j] = true;
                else
                {
                    v.push_back({i, j});
                    rest++;
                }
            }
        }
        if(rest%3)
        {
            cout<<0<<endl;
            continue;
        }
        cout<<bt(0, rest, v)<<endl;
    }
    return 0;
}