[백준 14500] 테트로미노

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

14500번: 테트로미노

 

요구사항

주어진 맵에서 이어진 4칸의 최대합 구하기

 

풀이

1. dfs로 4칸 정하기

2. 4칸의 합이 최대인지 검사

3. ㅏ모양은 dfs로 검사 안됨. ㅏ 모양이 되는 조건 확인

4. 정답 출력

 

 

#include <iostream>
#include <algorithm>

using namespace std;

int map[501][501];
int visit[501][501];
int n, m;
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,-1,0,1 };
int ans = 0;

void dfs(int r, int c, int cnt,int sum) {
	if (cnt == 4) {
		ans = max(ans, sum);
		return;
	}
	for (int i = 0; i < 4; i++) {
		int nr = r + dr[i];
		int nc = c + dc[i];
		if (nr < 0 || nc < 0 || nr >= n || nc >= m) {
			continue;
		}
		if (visit[nr][nc] == 0) {
			visit[nr][nc] = 1;
			dfs(nr, nc, cnt + 1, sum + map[nr][nc]);
			visit[nr][nc] = 0;
		}
	}
}
void sum1(int r, int c) {
	int temp = map[r][c] + map[r + 1][c] + map[r - 1][c] + map[r][c + 1];
	ans = max(ans, temp);
}
void sum2(int r, int c) {
	int temp = map[r][c] + map[r -1][c] + map[r][c-1] + map[r][c + 1];
	ans = max(ans, temp);
}
void sum3(int r, int c) {
	int temp = map[r][c] + map[r + 1][c] + map[r - 1][c] + map[r][c - 1];
	ans = max(ans, temp);
}
void sum4(int r, int c) {
	int temp = map[r][c] + map[r + 1][c] + map[r][c-1] + map[r][c + 1];
	ans = max(ans, temp);
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			visit[i][j] = 1;
			dfs(i, j, 1,map[i][j]);
			visit[i][j] = 0;
			if (i > 0 && i < n - 1 && j >= 0 && j < m - 1)
				sum1(i, j);

			if (i > 0 && i <= n - 1 && j > 0 && j < m - 1)
				sum2(i, j);

			if (i > 0 && i < n - 1 && j > 0 && j <= m - 1)
				sum3(i, j);

			if (i >= 0 && i < n - 1 && j > 0 && j < m - 1)
				sum4(i, j);

		}
	}
	cout << ans << endl;
}