반응형
풀이 )
먼저 입력받은 '.'의 개수를 세서 3으로 나누어떨어지지 않는 경우 '0'을 출력하고 종료한다.
'.'의 개수를 3으로 나누어 보드에 들어가는 총 블록의 수를 세고, DFS로 보드에 블록을 채워준다.
DFS 함수 내에서는 기저사례로 남은 블록 수가 0일 때 1을 반환하게 한다.
board에서 위에서부터 보면서 첫 '.'을 찾고, 그 위치에서 4종류의 블록을 넣어보면서 다음 블록을 채워 넣는다.
#include <iostream>
#include <string>
using namespace std;
int block[4][3][2] = {
{{0, 0}, {1, 0}, {1, 1}},
{{0, 0}, {0, 1}, {1, 1}},
{{0, 0}, {1, 0}, {0, 1}},
{{0, 0}, {1, 0}, {1, -1}}
};
int h, w;
int dfs(string board[], int numBlock){
if(!numBlock)
return 1;
int x = -1, y = -1;
for(int i = 0; i < h; ++i){
for(int j = 0; j < w; ++j){
if(board[i][j] == '.'){
x = i;
y = j;
break;
}
}
if(y != -1)
break;
}
int ret = 0;
for(int i = 0; i < 4; ++i){
bool flag = 0;
for(int j = 0; j < 3; ++j){
int nx = x+block[i][j][0];
int ny = y+block[i][j][1];
if(nx < 0 || nx >= h || ny < 0 || ny >= w || board[nx][ny] == '#'){
flag = true;
break;
}
}
if(flag)
continue;
for(int j = 0; j < 3; ++j){
int nx = x+block[i][j][0];
int ny = y+block[i][j][1];
board[nx][ny] = '#';
}
ret += dfs(board, numBlock-1);
for(int j = 0; j < 3; ++j){
int nx = x+block[i][j][0];
int ny = y+block[i][j][1];
board[nx][ny] = '.';
}
}
return ret;
}
int main(void){
int c;
cin >> c;
while(c--){
cin >> h >> w;
string* board = new string[h];
int numBlock = 0;
for(int i = 0; i < h; ++i){
cin >> board[i];
for(int j = 0; j < w; ++j){
if(board[i][j] == '.')
numBlock++;
}
}
if(numBlock%3){
cout << 0 << '\n';
continue;
}
numBlock/=3;
cout << dfs(board, numBlock) << '\n';
}
}
반응형
'문제풀이 > 알고스팟' 카테고리의 다른 글
[C++] 알고스팟 - CLOCKSYNC (0) | 2020.12.28 |
---|---|
[C++] 알고스팟 - PICNIC (0) | 2020.11.01 |
[C++] 알고스팟 - FESTIVAL (0) | 2020.03.09 |