[백준/BOJ] 백준 14391번 : 종이 조각

www.acmicpc.net/problem/14391

14391번: 종이 조각

게임판을 덮는 문제와 비슷하게 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int n, m;
vector<string> board;
int dxdy[7][4][2] = {
{{0,0},{0,0},{0,0},{0,0} }, //한칸 type=0
{{0,0},{0,1},{0,0},{0,0}}, //가로 두칸 type=1
{{0,0},{0,1},{0,2},{0,0}}, //가로 세칸 type=2
{{0,0},{0,1},{0,2},{0,3}}, //가로 네칸 type=3
{{0,0},{1,0},{0,0},{0,0}}, //세로 두칸 type=4
{{0,0},{1,0},{2,0},{0,0}}, //세로 세칸 type=5
{{0,0},{1,0},{2,0},{3,0}} //세로 네칸 type=6
};

//게임판 덮는 문제랑 비슷하게 풀기
//알고리즘 문제해결 전략1 무식하게 풀기 참고
//put:1 덮기, put:-1 덮은거 치우기
int Set_board(pair<int, int> here, vector<vector<int>>& check_board, int type, int put)
{
	bool check = true; //type 방법으로 덮을 수 있는지 확인
	string maked_num = "";
	int ret_num;
	int loop_num;

	if (type <= 3) //한칸 또는 가로 일 경우
		loop_num = type + 1;
	else //세로일 경우
		loop_num = type - 2;

	for (int i = 0; i < loop_num; i++)
	{
		pair<int, int> there = make_pair(here.first + dxdy[type][i][0], here.second + dxdy[type][i][1]);

		//범위를 넘어가지 않을때
		if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < m)
		{
			maked_num += board[there.first][there.second]; //해당 숫자 추가

			if (check_board[there.first][there.second] >= 1) //이미 덮여 있을때
				check = false;

			check_board[there.first][there.second] += put; //이미 덮여 있던 안덮여 있던 일단 추가로 덮는다 (나중에 뺄때를 위해)
		}

		//덮을 수 없을때
		else
		{
			check = false;
		}
	}

	if (check == false)
		return -1;

	ret_num = stoi(maked_num);

	return ret_num;
}

int Solve(vector<vector<int>>& check_board, int sum)
{
	bool find_point = false;
	pair<int, int> point;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (check_board[i][j] == 0)
			{
				find_point = true;
				point = make_pair(i, j);
				break;
			}
		}

		if (find_point == true)
			break;
	}

	//빈칸이 없을때
	if (find_point == false)
		return sum;

	int ret = 0;
	//point칸 7가지 방법으로 덮기
	for (int i = 0; i < 7; i++)
	{
		int maked_num = Set_board(point, check_board, i, 1);
		if (maked_num != -1) //i방법으로 덮을 수 있을때
		{
			ret = max(ret, Solve(check_board, sum + maked_num));
		}

		//덮은거 빼기
		Set_board(point, check_board, i, -1);
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		string input;
		cin >> input;

		board.push_back(input);
	}

	vector<vector<int>> check_board(n, vector<int>(m, 0));

	cout << Solve(check_board, 0);

	return 0;
}