백준 14500 테트로미노

설계 과정 1. 문제를 정확히 읽습니다. 2. 설계를 명확히 합니다. (예제 3개 돌리기) 3. 경우의 수를 나열합니다. 4. 초기화조건을 확인합니다. 5. 가지치기를 합니다. 6. 예제와 동일하게 변수를 선언하고 사용합니다. 풀이 과정 1. dfs 를 사용할 때, 이어질 수 있도록, 안에서 변수를 선언합니다. 2. star 표시 할때 주의할점 있습니다. (아이디어) - dfs 사용시 가지고 다니는 변수와, 돌아왔을 때 그자리에 존재하는 것들을 명확히 합니다. - 특히나 비짓과 관련된 변수는, 그 자리에 그대로 있어야 합니다.

/*
17:51 14500 테트로미노 
18:36
45분컷

설계 과정
1. 문제를 정확하게 읽습니다.
2. 설계를 완벽하게 합니다. (예제 3개 돌리기)
3. 경우의 수를 나열합니다. (자세히)
4. 초기화 조건을 확인합니다.
5. 가지치기를 합니다.
6. 예제와 같이 변수를 선언하고 사용합니다.

풀이 과정
1. dfs 를 돌려서 뎁스4일때의 섬을 저장합니다.
2. star 모양을 돌려서 최대값을 찾습니다.
3. 1과 2에서 찾은 값들 중 최대값을 찾습니다.

*/
 
#include <iostream>
#include <algorithm>
using namespace std;
#define SIZE 505// 505
int map[SIZE][SIZE];
int visit[SIZE][SIZE];
int maxVal;
int N, M;
int minVal;
int star_sum;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
void problemIn() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> map[i][j];
        }
    }
}
 
void init() {
 
}
 
void dfs(int depth, int sum, int x, int y) {
 
    if (depth == 4) {
        maxVal = max(maxVal, sum);
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 1 || ny < 1 || nx > N || ny > M) continue;
        if (visit[nx][ny] == 0) {
            visit[nx][ny] = 1;
            dfs(depth + 1, sum + map[nx][ny], nx, ny);
            visit[nx][ny] = 0;
        }
    }
}
 
 
void solve() {
 
    // depth 4 dfs 돌리기.
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            visit[i][j] = 1;
            dfs(1, map[i][j], i, j);
            visit[i][j] = 0;
        }
    }
 
    // star 모양찾기
    
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= M; j++) {
            star_sum = 0;
            minVal = 2123456789;
 
            if (i == 1 && j == 1) continue;
            else if (i == 1 && j == M) continue;
            else if (i == N && j == 1) continue;
            else if (i == N && j == M) continue;
 
            star_sum = map[i][j] + map[i - 1][j] + map[i + 1][j] + map[i][j + 1] + map[i][j - 1];
            minVal = min(minVal, map[i][j + 1]);
            minVal = min(minVal, map[i][j - 1]);
            minVal = min(minVal, map[i + 1][j]);
            minVal = min(minVal, map[i - 1][j]);
            star_sum -= minVal;
            maxVal = max(maxVal, star_sum);
        }
    }
 
}
 
int main() {
    problemIn();
    solve();
    cout << maxVal << endl;
    return 0;
}