알고스팟 - 게임판 덮기 (BOARDCOVER) [C++]

 이 문제 역시 완전 탐색을 이용해서 풀 수 있다. 이 문제의 핵심은 왼쪽, 위 모두 꽉 차있는 상태에서 재귀가 이뤄진다고 고정하고 문제를 푸는 것이다. 구현이 약간 복잡하지만 로직 자체는 단순한 문제였다.

 

#include <iostream>
#include <utility>

using namespace std;

#define MAX 20

int H, W;

pair<int, int> block[4][3] = {
	{{0, 0}, {1, 0}, {1, -1}},
	{{0, 0}, {1, 0}, {1, 1}},
	{{0, 0}, {0, 1}, {1, 1}},
	{{0, 0}, {0, 1}, {1, 0}}
};

char matrix[MAX][MAX];
bool assigned[MAX][MAX];

bool inRange(int y, int x) {
	if (0 <= y && y < H && 0 <= x && x < W) {
		return true;
	}
	return false;
}

bool check(int y, int x, int type) {
	for (pair<int, int>& dist : block[type]) {
		int dy = y + dist.first;
		int dx = x + dist.second;

		if (!inRange(dy, dx)) {
			return false;
		}

		if (assigned[dy][dx]) {
			return false;
		}

		if (matrix[dy][dx] == '#') {
			return false;
		}
	}

	return true;
}

void assign(int y, int x, int type, bool flag) {
	for (pair<int, int> &dist : block[type]) {
		int dy = y + dist.first;
		int dx = x + dist.second;

		assigned[dy][dx] = flag;
	}
}

pair<int, int> nextPos(int y, int x) {
	for (int h = y; h < H; h++) {
		if (h == y) {
			for (int w = x; w < W; w++) {
				if (!assigned[h][w] && matrix[h][w] == '.') {
					return { h, w };
				}
			}
			continue;
		}

		for (int w = 0; w < W; w++) {
			if (!assigned[h][w] && matrix[h][w] == '.') {
				return { h, w };
			}
		}
	}

	return { -1, -1 };
}

bool covered() {
	for (int y = 0; y < H; y++) {
		for (int x = 0; x < W; x++) {
			if (matrix[y][x] == '.' && !assigned[y][x]) {
				return false;
			}
		}
	}

	return true;
}

int solve(int y, int x, int whiteCount) {
	if (y == -1 && x == -1) {
		if (covered()) {
			return 1;
		}
		return 0;
	}

	int result = 0;
	for (int type = 0; type < 4; type++) {
		if (check(y, x, type)) {
			assign(y, x, type, true);
			pair<int, int> next = nextPos(y, x);
			result += solve(next.first, next.second, whiteCount - 3);
			assign(y, x, type, false);
		}
	}

	return result;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int C;

	cin >> C;

	for (int test = 0; test < C; test++) {
		cin >> H >> W;

		int whiteCount = 0;

		for (int y = 0; y < H; y++) {
			for (int x = 0; x < W; x++) {
				char c;

				cin >> c;

				if (c == '.') {
					whiteCount++;
				}
				matrix[y][x] = c;
			}
		}

		int startY = -1, startX = -1;
		for (int y = 0; y < H; y++) {
			for (int x = 0; x < W; x++) {
				if (matrix[y][x] == '.') {
					startY = y;
					startX = x;
					break;
				}
			}

			if (startY != -1) {
				break;
			}
		}

		if (whiteCount % 3 != 0) {
			cout << 0 << '\n';

			continue;
		}

		int answer = solve(startY, startX, whiteCount);

		cout << answer << '\n';
	}

	return 0;
}