[DFS] 백준 테트로미노 C++

 

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

14500번: 테트로미노

 

#include <iostream>
#include <vector>

using namespace std;

int n, m, answer;
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
int arr[500][500];
bool visited[500][500];

void dfs(int depth, int x, int y, int sum) {
	if ((x < 0) || (y < 0) || (x >= m) || (y >= n)) return;
	if (visited[y][x]) return;

	if (depth == 4) {
		answer = max(answer, sum);
		return;
	}

	visited[y][x] = true;
	for (int i = 0; i < 4; i++) dfs(depth + 1, x + dx[i], y + dy[i], sum + arr[y][x]);
	visited[y][x] = false;
}

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

	cin >> n >> m;

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

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			dfs(0, j, i, 0);

			// + 모양 테트리스 합
			int cross = arr[i][j];
			int cnt = 0;
			for (int k = 0; k < 4; k++) {
				int newX = j + dx[k];
				int newY = i + dy[k];
				if ((newX < 0) || (newY < 0) || (newX >= m) || (newY >= n)) continue;
				cross += arr[newY][newX];
				cnt++;
			}
			if (cnt == 3) {
				answer = max(answer, cross); // 벽에 붙은 ㅗ 모양
				continue;
			}
			if (cnt != 4) continue; // + 모양 아닐 때

			// ㅗ 모양 테트리스 예외
			answer = max(answer, cross - arr[i - 1][j]);
			answer = max(answer, cross - arr[i + 1][j]);
			answer = max(answer, cross - arr[i][j - 1]);
			answer = max(answer, cross - arr[i][j + 1]);
		}
	}

	cout << answer;
	
	return 0;
}