백준 14500 테트로미노

문제링크

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

문제

풀이

맵 크기가 500*500 이고 블록의 모든 경우의 수는 19가지 이므로
dfs를 이용해 완전 탐색을 하더라도 시간초과가 나지 않는다.
단, dfs로는 ㅏ ㅓ ㅗ ㅜ 모양은 탐색할 수 없으므로
이 경우는 따로 구현을 해주었다.

코드

#include <iostream>
using namespace std;

int maps[501][501];
bool vi[501][501];
int n, m;
int dx[4]{ 0,0,1,-1 };
int dy[4]{ 1,-1,0,0 };

int btrc(int cnt, int x, int y,int sumn) {

	if (cnt == 4) {
		return sumn;
	}

	int maxn = 0;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vi[nx][ny]) {
			vi[nx][ny] = true;
			maxn=max(maxn,btrc(cnt + 1, nx, ny,sumn+maps[nx][ny]));
			vi[nx][ny] = false;
		}
	}

	return maxn;
}

int exshape(int x,int y) {
	int maxn = 0;
	if (x - 1 >= 0 && x < n && y - 1 >= 0 && y + 1 < m) {
		maxn = max(maxn, maps[x - 1][y] + maps[x][y - 1] + maps[x][y] + maps[x][y + 1]);
	}

	if (x >= 0 && x + 1 < n && y - 1 >= 0 && y + 1 < m) {
		maxn = max(maxn, maps[x+1][y] + maps[x][y - 1] + maps[x][y] + maps[x][y + 1]);
	}

	if (x - 1 >= 0 && x + 1 < n && y >= 0 && y + 1 < m) {
		maxn = max(maxn, maps[x][y + 1] + maps[x - 1][y] + maps[x][y] + maps[x + 1][y]);
	}

	if (x - 1 >= 0 && x + 1 < n && y - 1 >= 0 && y < m) {
		maxn = max(maxn, maps[x][y - 1] + maps[x - 1][y] + maps[x][y] + maps[x + 1][y]);
	}
	return maxn;
}

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

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> maps[i][j];
		}
	}

	int maxn = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			vi[i][j] = true;
			maxn = max(maxn,btrc(1, i, j, maps[i][j]));
			maxn = max(maxn, exshape(i, j));
			vi[i][j] = false;
		}
	}
	cout << maxn;

}

시행착오

ㅏ ㅓ ㅗ ㅜ 모양에 대한 예외를 생각하지 못하고 첫시도 후 실패

저번에 백준 1941 소문난 칠공주 문제를 풀었을때도 dfs로 시도를 해보려다 저렇게 중간에 빠져나오는 모양은 dfs로 탐색이 어렵다는것을 깨달아서 이번에 오류를 찾는데 오랜 시간이 걸리지 않았다.