[BAE/<JOON> 문제풀이] 14500. 테트로미노

https://www.acmicpc.net/problem/14500

14500번: 테트로미노

간단한 백트래킹 문제였다.

 

한가지 다른점은 엿모양 블럭은 한붓그리기가 안되기 때문에 다른 방법을 써야한다는 점이다.

 

(ㄴ 모양이나 ㅁ, ㅣ 모양, ㄹ 모양은 모두 한붓그리기가 된다.) 

 

효율적인 방법을 고민하다가, 그냥 간단하게 두번째 블럭을 체크할 때 [위, 오른쪽], [아래, 왼쪽] 을 동시에 더하고 체크하는 루틴을 만들어 해결했다.

 

#include <iostream>
#include <vector>

/*
엿모양은 한붓그리기가 안됨
따로 찾아야됨
*/

using namespace std;

vector<vector<int> > arr;
vector<vector<int> > ch;
int n, m;

int mx = -99;

bool r(int x, int y, int cnt, int sum) {
	if (x > n || x < 1 || y > m || y < 1) return false;
	if (ch[x][y] == 1) return false;
	if (cnt == 3) {
		if (mx < sum) mx = sum;
		return true;
	}
	ch[x][y] = 1;
	if (x + 1 <= n) {
		r(x + 1, y, cnt + 1, sum + arr[x + 1][y]);
	}
	if (y + 1 <= m) {
		r(x, y + 1, cnt + 1, sum + arr[x][y + 1]);
	}
	if (x - 1 >= 1) {
		r(x - 1, y, cnt + 1, sum + arr[x - 1][y]);
	}
	if (y - 1 >= 1) {
		r(x, y - 1, cnt + 1, sum + arr[x][y - 1]);
	}
	if (cnt == 1) {//엿모양 검사
		if (x + 1 <= n && y + 1 <= m && ch[x + 1][y] == 0 && ch[x][y + 1] == 0) {
			r(x, y + 1, cnt + 2, sum + arr[x + 1][y] + arr[x][y + 1]);
			r(x + 1, y, cnt + 2, sum + arr[x + 1][y] + arr[x][y + 1]);
		}
		if (x - 1 >= 1 && y - 1 >= 1 && ch[x - 1][y] == 0 && ch[x][y - 1] == 0) {
			r(x, y - 1, cnt + 2, sum + arr[x - 1][y] + arr[x][y - 1]);
			r(x - 1, y, cnt + 2, sum + arr[x - 1][y] + arr[x][y - 1]);
		}
	}
	ch[x][y] = 0;
	return true;
}

int main()
{
	cin >> n >> m;
	arr.resize(n + 1);
	ch.resize(n + 1);
	for (int i = 1; i <= n; i++) {
		arr[i].resize(m + 1);
		ch[i].resize(m + 1);
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {			
			r(i, j, 0, arr[i][j]);			
		}
	}

	cout << mx << endl;

	return 0;
}