[algospot][완전탐색] 게임판 덮기 : https://algospot.com/judge/problem/read/BOARDCOVER

BOARDCOVER.cpp

#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include<iostream>

using namespace std;

int H, W;
int block[4][2][3] = {
	{ { 0, 1, 0 },{ 0, 1, 1 } },
	{ { 0, 1, 1 },{ 0, 1, 0 } },
	{ { 0, 1, 1 },{ 0, 0, 1 } },
	{ { 0, 1, 0 },{ 1, 1, 0 } },
};

bool validateBoundary(int x, int y) {
	if (x < 0 || y < 0) return false;
	return (x < H && y < W);
}

vector<string> setBlock(int ind, int x, int y, vector<string> arr) {
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 3; j++) {
			if (block[ind][i][j] == 0) continue;
			if (!validateBoundary(x + i, y - 1 + j) || 
				arr[x + i][y - 1 + j] == '#') return vector<string>();
			arr[x + i][y - 1 + j] = '#';
		}
	}
	return arr;
}

int solve(vector<string> arr) {
	int x = -1;
	int y = -1;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (arr[i][j] == '#') continue;
			x = i; y = j;
			break;
		}
		if (x != -1) break;
	}

	// can answer
	if (x == -1) return 1;

	int ans = 0;
	for (int k = 0; k < 4; k++) {
		vector<string> nextArr = setBlock(k, x, y, arr);
		if (nextArr.size() != 0) {
			ans += solve(nextArr);
		}
	}

	return ans;
}

int main() {
	int C;
	cin >> C;

	while (C--) {
		
		cin >> H >> W;
		vector<string> arr = vector<string>(H);
		for (int i = 0; i < H; i++)
			cin >> arr[i];
		cout << solve(arr) << endl;
	}
	return 0;
}