BOJ 14500 [테트로미노]

BOJ 테트로미노 : https://www.acmicpc.net/problem/14500

안녕하세요. 이번 문제는 백준 온라인 저지의 [테트로미노] 입니다.

먼저, 위 그림의 핑크색 모양 블록을 제외하면, 나머지 4개 모양의 블록은 모두 DFS를 통해 찾아낼 수 있습니다.

1. 한 점을 잡고, 중복을 어느정도 최소화하기 위해 위로 가지 않도록 DFS를 진행한다.

2. 그러면 한 점에서 갈 수 있는 모든 블록 (ㅗ 모양 블록 제외 //욕 아닙니다 :) )을 탐색할 수 있다.

3. ㅗ 모양 블록은, 해당 점에서 십자가를 그린 뒤, 최소값을 가진 블록을 뺀 값.

//함수 이름이 부적절할 수 있습니다.

#include <iostream>
using namespace std;
int N, M;
int Map[500][500];
bool Visited[500][500];
int dx[3] = {1, 0, 0};
int dy[3] = {0, 1, -1};
int fuck_x[4] = {1, 0, -1, 0};
int fuck_y[4] = {0, 1, 0, -1};
int Result = 0;
void DFS(int i, int j, int depth, int sum) {
    if(depth == 4) {
        Result = Result > sum ? Result : sum;
        return;
    }
    for(int k=0; k<3; k++) {
        if(i + dx[k] >= 0 && i + dx[k] < N && j + dy[k] >= 0 && j + dy[k] < M) {
            if(!Visited[i + dx[k]][j + dy[k]]) {
                Visited[i + dx[k]][j + dy[k]] = true;
                DFS(i+dx[k], j+dy[k], depth+1, sum + Map[i+dx[k]][j+dy[k]]);
                Visited[i + dx[k]][j + dy[k]] = false;
            }
        }
    }
}
void Fuck(int i, int j) {
    int Min = 1000;
    int cnt = 0;
    int sum = Map[i][j];
    for(int k=0; k<4; k++) {
        if(i + fuck_x[k] >= 0 && i + fuck_x[k] < N && j + fuck_y[k] >= 0 && fuck_y[k] < M) {
            cnt++;
            sum += Map[i + fuck_x[k]][j + fuck_y[k]];
            if(Min > Map[i + fuck_x[k]][j + fuck_y[k]])
                Min = Map[i + fuck_x[k]][j + fuck_y[k]];
        }
    }
    if(cnt != 4) Min = 0;
    Result = Result > (sum - Min) ? Result : (sum - Min);
}
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++) {
            Visited[i][j] = true;
            DFS(i, j, 1, Map[i][j]);
            Visited[i][j] = false;
            Fuck(i, j);
        }
    }
    cout << Result << endl;
    return 0;
}