BOARDCOVER

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

algospot.com :: BOARDCOVER

 

완전탐색 문제이다. 그런데 경우의 수를 어떻게 중복없이 체계적으로 셀 수 있을까? 순서를 강제하면 된다.

게임판의 빈 부분을 좌상단부터 하나씩 채워나간다. 이 때 모든 빈 부분이 덮어지면 경우의 수를 하나 더해준다.

아래 그림에서 별표 부분을 덮는다고 가정하자. 이 때 별표 왼쪽 부분까지는 다 채워져 있다. 그러면 L자 모양의 블록을 덮는 경우가 4가지이고 모두 가능한지 확인해보면 된다. delta에 따라 블록을 덮거나 치울 수 있다.

 

 

#include <cstdio>

int t,h,w,map[55][55];
char tmap[55][55];
int coverType[4][3][2]={
    {{0,0},{1,0},{0,1}},
    {{0,0},{0,1},{1,1}},
    {{0,0},{1,0},{1,1}},
    {{0,0},{1,0},{1,-1}}
};

bool set(int x,int y,int type,int delta)
{
    bool ok=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 || nx>=h || ny<0 || ny>=w || (map[nx][ny]+=delta)>1)
            ok=false;
    }
    return ok;
}

int cover()
{
    int x=-1,y=-1;
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            if(map[i][j]==0)
            {
                x=i,y=j;
                break;
            }
        }
        if(x!=-1 && y!=-1) break;
    }
    if(x==-1 && y==-1) return 1;
    int ret=0;
    for(int type=0;type<4;type++)
    {
        if(set(x,y,type,1))
            ret+=cover();
        set(x,y,type,-1);
    }
    return ret;
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&h,&w);
        for(int i=0;i<h;i++)
            scanf("%s",tmap[i]);
        for(int i=0;i<h;i++)
            for(int j=0;j<w;j++)
                map[i][j]=(tmap[i][j]=='#')?1:0;
        printf("%d\n",cover());
    }
    return 0;
}