백준 14500문제

#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i=a ; i<b ; i++)

int x[4] = {0,-1,1,0};
int y[4] = {1,0,0,-1};

int N,M,A[501][501],ANS;
int v[501][501];

bool check(int a, int b){
    return (a>=0 && a<N && b>=0 && b <= M);
}
void ex(int a, int b){
    int s=A[a][b],m=1e9,cnt=0;
    FOR(i,0,4){
        int nx = a+x[i], ny = b+y[i];
        if(!check(nx,ny)) continue;
        s += A[nx][ny];
        m = min(m,A[nx][ny]);
        cnt++;
    }
    if(cnt==4) ANS = max(ANS,s - m);
    else if(cnt == 3) ANS = max(ANS,s);

}
void dfs(int a, int b, int depth, int cur){
    if(depth == 4){
        ANS = max(ANS,cur);
        return;
    }
    v[a][b] = 1;
    FOR(i,0,3){
        int nx = a + x[i] , ny = b + y[i];
        if(!v[nx][ny] && check(nx,ny))
            dfs(nx,ny,depth + 1,cur+A[nx][ny]);
    }
    v[a][b] = 0;
}

int main(){
    ios_base::sync_with_stdio(false);

    cin >> N >> M;
    FOR(i,0,N) FOR(j,0,M) cin >> A[i][j];
    FOR(i,0,N) FOR(j,0,M){
        dfs(i,j,1,A[i][j]);
        ex(i,j);
    }
    cout << ANS << endl;
    return 0;
}

백준 테트로미노 문제 풀이입니다.