백준 - 테트로미노(14500)

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

 

 

골드4티어 문제이다.

 

 

 

한 점에서 4칸까지 움직일 동안 DFS로 탐색을 진행하면

T모양을 제외한 모든 모양을 만들 수 있다.

최댓값을 구해주고

 

나중에 T모양을 따로 탐색을 진행해 준다.

T 같은 경우는 십자가 모양을 전부 더해서 최솟값을 빼준다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
vector<vector<int>> graph;
vector<vector<int>> visited;
int n, m;

int dy[4] = {0, 1, -1, 0};
int dx[4] = { 1, 0, 0, -1 };
int answer = -1;


void dfs(int cnt, int total, int y, int x)
{
	if (cnt == 4) {
		answer = answer < total ? total : answer;
	}
	else {
		for (int i = 0; i < 4; i++) {
			int cur_y = y + dy[i];
			int cur_x = x + dx[i];

			if (cur_y < 0 or cur_y >= n or cur_x < 0 or cur_x >= m) continue;
			if (visited[cur_y][cur_x]) continue;

			visited[cur_y][cur_x] = 1;
			dfs(cnt + 1, total + graph[cur_y][cur_x], cur_y, cur_x);
			visited[cur_y][cur_x] = 0;
		}
	}

	
}



int main() {	
	cin >> n >> m;

	graph.assign(n, vector<int>(m, 0));
	visited.assign(n, vector<int>(m, 0));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> graph[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			visited[i][j] = 1;
			dfs(1, graph[i][j], i, j);
			visited[i][j] = 0;
		}
	}
	
	

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int total = graph[i][j];

			int min_data = 1001;
			for (int k = 0; k < 4; k++) {
				
				if (i + dy[k] < 0 or i + dy[k] >= n or j + dx[k] < 0 or j + dx[k] >= m)
				{	
					min_data = 0;
					continue;
				}

				min_data = min(min_data, graph[i + dy[k]][j + dx[k]]);
				total += graph[i + dy[k]][j + dx[k]];
			}

			answer = answer < total - min_data ? total - min_data : answer;

		}
	}

	cout << answer;
}