[종만북] 게임판덮기(BOARD COVER) (C++)

문제 출처 :

algospot.com/judge/problem/read/BOARDCOVER

algospot.com :: BOARDCOVER

문제 풀이 :

jinu0418.tistory.com/28

[종만북] 게임판덮기(BOARD COVER) (Python)

에 쓰여있는 것과 같은 로직으로 풀었다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

const int blocks[4][3][2]={
        {{0,0},{1,0},{1,1}},{{0,0},{0,1},{1,0}},
        {{0,0},{0,1},{1,1}},{{0,0},{1,-1},{1,0}}
};
vector<vector<int>> board={};

bool set(vector<vector <int>>& board, int y, int x, int type, int delta)
{
    bool ok = true;
    for(int i=0; i<3 ; i++)
    {
        const int ny = y+blocks[type][i][0];
        const int nx = x+blocks[type][i][1];

        if(ny<0 || ny >= board.size() || nx <0 || nx>=board[0].size())
        {
            ok = false;
        }
        else if((board[ny][nx] += delta) >1) {
            ok = false;
        }
    }
    return ok;
}

int cover(vector<vector<int>> &board)
{
    int y=-1;
    int x=-1;
    bool start_condition = false;

    for(int i =0;i<board.size();i++)
    {
        for(int j =0;j<board[0].size();j++)
        {
            if(board[i][j]==0)
            {
                y=i;
                x=j;
                start_condition = true;
                break;
            }
        }
        if(start_condition){
            break;
        }
    }

    if(y==-1)
    {
        return 1;
    }

    int ret = 0;
    for(int type =0; type<4;type++)
    {
        if(set(board,y,x,type,1))
        {
            ret += cover(board);
        }
        set(board,y,x,type,-1);
    }
    return ret;
}
int main(){
    int C=0;
    int h,w;
    int cnt_white=0;
    h=w=0;
    cin >> C;
    string tmp_input;
    for(int cnt=0;cnt<C;cnt++)
    {
        cnt_white=0;
        h=w=0;
        tmp_input ={};
        vector<vector<int>> board={};
        cin >>h>>w;
        for(int tmp1=0; tmp1 <h;tmp1++)
        {
            cin >> tmp_input;
            vector<int> tmp_vec={} ;
            for(int tmp2=0;tmp2<w;tmp2++)
            {
                if(tmp_input[tmp2]=='#')
                {
                    tmp_vec.push_back(1);
                }
                else
                {
                    cnt_white++;
                    tmp_vec.push_back(0);
                }
            }
            board.push_back(tmp_vec);
        }
        if(cnt_white%3!=0)
        {
            cout << 0<<'\n';
            continue;
        }
        int ans = 0;
        ans = cover(board);
        cout << ans<<"\n";
    }
    return 0;
}