[algospot] BOARDCOVER

문제링크 입니다

[BOARDCOVER] 문제

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

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

입력

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

출력

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

예제 입력

3
3 7
#.....#
#.....#
##...##
3 7
#.....#
#.....#
##..###
8 10
##########
#........#
#........#
#........#
#........#
#........#
#........#
##########

예제 출력

0
2
1514

전체 코드는 다음과 같습니다.

//
//  BOARDCOVER.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/09/02.
//

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

int H, W =0;
ifstream fin("test_boardcover.txt");

// const int cover[4][3][2] 생략 책 참고바람,,, 블로그 오류가 뜨네요 '}' 관련..
// first ( x,y ) ( x+1,y ) ( x+1,y+1)

bool set(vector<vector <int > >& board, int x, int y , int type, int delta){
    bool ok = true;
    for(int i=0; i< 3; i++){
        const int temp_x = x + cover[type][i][1];
        const int temp_y = y + cover[type][i][0];
        if( temp_y <0 || temp_y >=board.size() || temp_x<0 || temp_x >= board[0].size() ){
            ok = false;
        }
        else if((board[temp_y][temp_x] +=delta ) > 1){
            ok = false;
        }
    }
    return ok;
}

void reset(vector<vector <int > > board,int x, int y,int type){
    for(int i=0; i< 3; i++){
        int temp_x = x + cover[type][i][1];
        int temp_y = y + cover[type][i][0];
        board[temp_y][temp_x] = 0;

    }
}
void set_1(vector<vector <int > > board, int x, int y,int type){
    for(int i=0; i< 3; i++){
        int temp_x = x + cover[type][i][1];
        int temp_y = y + cover[type][i][0];
        board[temp_y][temp_x] = 1;
    }
}


int boardcover (vector<vector <int> >& board){
    int y = -1, x = -1;
    for(int i=0; i< H; i++){
        for(int j=0; j<W; j++){
            if(board[i][j]==0){
                y = i;
                x = j;
                break;
            }
        }
        if(y != -1) break;
    }
    if( y == -1){
        return 1;
    }
    int ret=0;
    for(int i=0; i<4; i++){
        if(set(board, x, y, i,1)){
            ret+= boardcover(board);
        }
        set(board, x,y,i,-1);
    }
    return ret;
}
int main(int argc, const char * argv[]) {
    int Test_case;
    fin >> Test_case;
    for (int i=0; i< Test_case ; i++){
        fin >> H >> W;
        vector<vector <int> > board;
        int count = 0;
        char temp;
        for(int i = 0 ; i<H; i++){
            vector<int> small_board;
            for(int j=0; j<W; j++){
                fin >> temp;
                if(temp == '.'){
                    small_board.push_back(0);
                    count ++;
                }
                else if (temp =='#'){
                    small_board.push_back(1);
                }
            }
            board.push_back(small_board);
        }
        if(count % 3 != 0)
            cout << 0 << endl;
        else
            cout << boardcover(board) << endl;

    }
    return 0;
}