boardcover, 하

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

algospot.com :: BOARDCOVER

문제

• . 과 # 으로 이루어진 $h \times w (1\leq h, w \leq 20)$ 행렬이 주어진다
• 3칸짜리 블록으로 . 칸을 채울 때, 경우의 수는?

 

풀이

완전탐색

 

#include <bits/stdc++.h>
#define endl "\n"
#define ooop(i, n) for(int i = 0; i < n; i++)
#define loop(i, n) for(int i = 1; i <= n; i++)
using namespace std;
 
int h, w;
 
struct coords{
    int r1;
    int c1;
    int r2;
    int c2;
};
 
vector<coords> posible = {{1, 0, 1 ,-1},
                      {0, 1, 1, 1},
                      {1, 0, 1, 1},
                      {1, 0, 0, 1}
                      };
 
pair<int, int> first_white(vector<vector<char> >& d)
{
    ooop(r, h){
        ooop(c, w){
            if(d[r][c] == '.') return {r, c};
        }
    }
    return {-1, -1};
}
 
bool out_of_index(const int nr1, const int nr2, const int nc1, const int nc2)
{
    if(nr1 < 0 || nr1 >= h) return true;
    if(nr2 < 0 || nr2 >= h) return true;
    if(nc1 < 0 || nc1 >= w) return true;
    if(nc1 < 0 || nc1 >= w) return true;
    return false;
}
 
int countCovering(vector<vector<char> >& d)
{
    int fr = -1, fc = -1;
    tie(fr, fc) = first_white(d);
 
    if(fr == -1) return 1;
 
    int ret = 0;
    for(auto b: posible){
        int nr1 = fr+b.r1, nr2 = fr+b.r2, nc1 = fc+b.c1, nc2 = fc+b.c2;
        if(out_of_index(nr1, nr2, nc1, nc2)) continue;
        if(d[nr1][nc1] == '.' && d[nr2][nc2] == '.'){
            d[fr][fc] = d[nr1][nc1] = d[nr2][nc2] = '#';
            ret += countCovering(d);
            d[fr][fc] = d[nr1][nc1] = d[nr2][nc2] = '.';
        }
    }
 
    return ret;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        cin >> h >> w;
        vector<vector<char> > d(h, vector<char>(w));
 
        string row;
        int white = 0;
        ooop(r, h){
            cin >> row;
            ooop(c, w) {
                d[r][c] = row[c];
                if(d[r][c] == '.') white++;
            }
        }
 
        if(white % 3 == 0) cout << countCovering(d) << endl;
        else cout << 0 << endl;
    }
 
    return 0;
}cs