[알고스팟] 종만북 게임판 덮기 ID: BOARDCOVER

https://algospot.com/judge/submission/recent/

algospot.com :: 답안 목록

 

현재 좌표 x, y 가 비어있다면 x,y를 기준으로 블록을 놓을 수 있는 경우의 수는 4가지가 있습니다.

먼저 맨 위쪽이면서 가장 맨 왼쪽에 블럭을 놓을 수 잇는 게임판 좌표 x,y를 찾아 4가지 블록에 대하여 가능한 블록으로 덮고 DFS를 진행하면 됩니다.

cover 함수를 만들어서 flag가 1이면 해당 좌표에 블록을 두고 0이면 둔 블록을 해제 하는 식으로 방문 배열 역할을 하게끔 만들었습니다. (이런 구현 이슈가 있는 문제들은 모듈화 시켜놓는 것이 좋습니다.)

또한 게임판 밖으로 좌표가 벗어나면 안되므로 아래 조건이 추가되어야 합니다.

			if (_x < 0 || _y < 0 || _x >= n || _y >= m || map[_x][_y] != '.') {
				can_cover = 0;
				break;
			}

 

#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;

int nx[4][3] = { {0,1,1}, {0,0,1}, {0,0,1}, {0,1,1} };
int ny[4][3] = { {0,-1,0}, {0,1,0}, {0,1,1}, {0,0,1} };
char map[21][21];
int ans,n,m;
inline void cover(int x, int y, int idx,int flag) {
	for (int j = 0; j < 3; j++) {
		int _x = x+nx[idx][j];
		int _y = y+ny[idx][j];
		map[_x][_y] = (flag ? 'C' : '.');
	}
	return;
}
void dfs(int x, int y) {
	if (map[x][y] != '.') {
		int flag = 0;
		for (int i = 0; !flag && i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == '.') {
					dfs(i, j);
					flag = 1;
					break;
				}
			}
		}
		if (!flag) {
			ans += 1;
			return;
		}
	}
	for (int i = 0; i < 4; i++) {
		int can_cover = 1;
		for (int j = 0; j < 3; j++) {
			int _x = x + nx[i][j];
			int _y = y + ny[i][j];
			if (_x < 0 || _y < 0 || _x >= n || _y >= m || map[_x][_y] != '.') {
				can_cover = 0;
				break;
			}
		}
		if (can_cover) { // 덮을 수 있음
			cover(x, y, i, 1);
			dfs(x, y);
			cover(x, y, i, 0);
		}
	}
}
void solve() {
	cin >> n >> m;
	ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}
	dfs(0, 0); // 0,0 부터 시작
	cout << ans << "\n";
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int C;
	cin >> C;
	for (; C--;) {
		solve();
	}
}