BOARDCOVER

#include <iostream>
#include <vector>

using namespace std;

const int MAX_WIDTH = 20;
const int coverType[4][3][2] = {
	{{0, 0}, {1, 0}, {1, -1}},
	{{0, 0}, {0, 1}, {1, 1}},
	{{0, 0}, {1, 0}, {1, 1}},
	{{0, 0}, {1, 0}, {0, 1}}
};

int boardHeight = 0, boardWidth = 0;

int cover(vector<vector<int>> &board);
bool set(vector<vector<int>> &board, int y, int x, int type, int flip);

int main()
{
	int caseNum = 0;
	string inputBuffer;
	char widthBuffer[MAX_WIDTH];

	vector<vector<int>> board;

	cin >> caseNum;

	for (int caseIter = 0; caseIter < caseNum; caseIter++)
	{
		cin >> boardHeight >> boardWidth;

		// clear cin
		cin.ignore();

		// clear buffer
		memset(widthBuffer, 0, MAX_WIDTH);

		// clear board
		board.clear();

		for (int hIter = 0; hIter < boardHeight; hIter++)
		{
			cin.getline(widthBuffer, MAX_WIDTH);

			// fill board data from input
			board.push_back(vector<int>(boardWidth));
			for (int wIter = 0; wIter < boardWidth; wIter++)
			{
				if (widthBuffer[wIter] == '#') { board[hIter][wIter] = 1; }
				else if(widthBuffer[wIter] == '.') { board[hIter][wIter] = 0; }
				else { cout << "Invalid Input" << endl; }
			}
		}

		cout << cover(board) << endl;
	}
}

int cover(vector<vector<int>> &board)
{
	int y = -1, x = -1;

	for (int i = 0; i < boardHeight; i++)
	{
		for (int j = 0; j < boardWidth; j++)
		{
			if (board[i][j] == 0)
			{
				y = i;
				x = j;
				break;
			}
		}
		if (y != -1) break;
	}
	
	if (y == -1) return 1;

	int ret = 0;
	for (int type = 0; type < 4; type++)
	{
		if (set(board, y, x, type, 1))
		{
			ret += cover(board);
		}
		set(board, y, x, type, -1);
	}

	return ret;
}

bool set(vector<vector<int>> &board, int y, int x, int type, int flip)
{
	bool ok = true;

	for (int i = 0; i < 3; i++)
	{
		int dy = y + coverType[type][i][0];
		int dx = x + coverType[type][i][1];
		if (dy < 0 || dy >= boardHeight || dx < 0 || dx >= boardWidth) ok = false;
		else if ((board[dy][dx] += flip) > 1) ok = false;
	}
	
	return ok;
}

board 에 놓여지는 블록들의 좌표를 coverType 으로 관리하여 간편하게 set() 을 할 수 있다. set() 함수는 "블록을 놓는 동작" 에 해당하며, cover() 함수는 빈칸이 발견되었을 때 (4가지 중) 어느 type 으로 블록을 놓을지를 결정하고, cover()를 재귀 호출한다.

또 하나 팁은, board는 2차원 vector 이므로 초기에 데이터를 넣어 줄 때 board[n].push_back(boardWidth) 을 호출하여 board의 width에 대한 메모리 할당을 한번 더 해주어야 한다. (2차원 배열을 선언할 때 큰 줄기를 메모리 할당하고, 각 가지들에게 한번 더 메모리를 할당하는 것과 같은 개념이다.)

boardInput.txt

boardOutput.txt