브루트포스 159p 게임판 덮기

algospot.com/judge/problem/read/BOARDCOVER

algospot.com :: BOARDCOVER

역시 완전탐색을 위한 문제.

 

중복을 피하기 위한 방법이 제일 중요한 문제였다. 가장 왼쪽 위부터 채워나갔다.

#include<iostream>
using namespace std;
#define MAX 25

int T, H, W;
bool game[MAX][MAX];

int solve(int num) {
	if (num == 0) return 1;

	int ret = 0;
	int i=-1, j=-1;

	for (int a = 1; a <= H; a++) {
		for (int b = 1; b <= W; b++) {
			if (game[a][b]) {
				i = a;
				j = b;
				break;
			}
		}
		if (i != -1)break;
	}

	game[i][j] = false;
	if (game[i][j + 1] && game[i + 1][j + 1]) {
		game[i][j + 1] = false;
		game[i + 1][j + 1] = false;
		ret += solve(num - 3);
		game[i][j + 1] = true;
		game[i + 1][j + 1] = true;
	}
	if (game[i + 1][j] && game[i + 1][j + 1]) {
		game[i + 1][j] = false;
		game[i + 1][j + 1] = false;
		ret += solve(num - 3);
		game[i + 1][j] = true;
		game[i + 1][j + 1] = true;
	}
	if (game[i + 1][j] && game[i][j + 1]) {
		game[i + 1][j] = false;
		game[i][j + 1] = false;
		ret += solve(num - 3);
		game[i + 1][j] = true;
		game[i][j + 1] = true;
	}
	if (game[i + 1][j] && game[i + 1][j - 1]) {
		game[i + 1][j] = false;
		game[i + 1][j - 1] = false;
		ret += solve(num - 3);
		game[i + 1][j] = true;
		game[i + 1][j - 1] = true;
	}
	game[i][j] = true;



	return ret;
}

int main() {
	cin >> T;
	while (T--) {
		for (int i = 0; i < MAX; i++) {
			for (int j = 0; j < MAX; j++) {
				game[i][j] = false;
			}
		}
		int cnt = 0;
		cin >> H >> W;
		for (int i = 1; i <= H; i++) {
			for (int j = 1; j <= W; j++) {
				char a;
				cin >> a;
				if (a == '.') {
					game[i][j] = true;
					cnt++;
				}
			}
		}
		if (cnt % 3 != 0) {
			cout << 0 << '\n';
			continue;
		}
		cout << solve(cnt) << "\n";
	}
}