[Brute-force]BOARDCOVER 게임판 덮기

 

#include <iostream>
 
bool gameboard[20][20] = {false, };
 
// y1, x1, y2, x2
int block[4][4] = {
    {1,-1, 1, 0},
    {1, 0, 1, 1},
    {1, 0, 0, 1},
    {0, 1, 1, 1}
};
bool isOkay(int h, int w, int y, int x)
{
    return ( (-1 < y && y < h) 
        && (-1 < x && x < w) 
        && gameboard[y][x]);
}
int coverBoardNum(int h, int w, int currenty, int currentx)
{
    int addBlock1x = 0, addBlock1y = 0, addBlock2x = 0, addBlock2y = 0, ret = 0;
 
    if(currenty == h) return 1;
 
    if(!gameboard[currenty][currentx])
    {
        if(currentx + 1 == w) return coverBoardNum(h, w, currenty + 1, 0);
        else return coverBoardNum(h, w, currenty, currentx+1);      
    }
 
    for(int i = 0; i < 4; i++)
    {
        addBlock1y = block[i][0] + currenty; addBlock1x = block[i][1] + currentx;
        addBlock2y = block[i][2] + currenty; addBlock2x = block[i][3] + currentx;
 
        if(isOkay(h, w, addBlock1y, addBlock1x) && isOkay(h,w, addBlock2y, addBlock2x))
        {
            gameboard[currenty][currentx] = false;
            gameboard[addBlock1y][addBlock1x] = false;
            gameboard[addBlock2y][addBlock2x] = false;
            
            ret += coverBoardNum(h,w,currenty, currentx);
            
            gameboard[currenty][currentx] = true;
            gameboard[addBlock1y][addBlock1x] = true;
            gameboard[addBlock2y][addBlock2x] = true;
        }
    }
    return ret;
}
 
int main(void)
{
    int testCase = 0, h = 0, w = 0;
    char input = 0;
 
    std::cin>>testCase;
 
    for(int i = 0; i < testCase; i++)
    {
        std::cin>>h>>w;
        for(int j = 0; j < h; j++)
        {
            for(int k = 0; k < w; k++)
            {
                std::cin>>input;
                if(input == '#')
                    gameboard[j][k] = false;
                else
                    gameboard[j][k] = true;
            }
        }
        std::cout<<coverBoardNum(h, w, 0, 0)<<std::endl;
    }
}

 

1. 완전탐색, 재귀

    특정한 순서를 강제해야한다

    0,0 에서 끝까지 지나가면서 지나간 곳은 항상 이미 채워져 있다고 가정해야한다.

2. 배열

3. 더 빨리 풀 수 있는지?

    입력받을 때 '.'의 위치를 스택이나 링크드 리스트에 저장하고 블록을 덮을 때 그 위치도 저장하면 불필요한 계산을 줄일 수 있을 것 이다.

    '.'이 3의 배수가 아니면 채울 수 없으므로 예외로 처리

BOARDCOVER