분명 첫 예제 답이 19가 나와야하는데 21이 나옴.... 그냥 dfs 부분에서 잘못된거같은데 뭐가 잘못됐는지 모르겠다;



#include <iostream>
#include <algorithm>
using namespace std;

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

int map[500][500];
bool visited[500][500];

int N, M;
int ans;

void dfs(int x, int y, int sum, int cnt)
{
    if(cnt==3)
    {
        ans=max(ans, sum);
        return;
    }
    
    for(int i=0; i<4; i++)
    {
        int nx=x+dx[i];
        int ny=y+dy[i];
        
        if(nx>=0 && nx<M && ny>=0 && ny<N)
        {
            if(visited[ny][nx]==false)
            {
                visited[ny][nx]=true;
                dfs(nx, ny, sum+map[ny][nx], cnt+1);
                visited[ny][nx]=false;
            }
        }
    }
}

void exceptiondfs(int x, int y)
{
    if(x+2<M && y+1<N)
        ans=max(ans, map[y][x]+map[y][x+1]+map[y][x+2]+map[y+1][x+1]);
        
    if(x+2<M && y-1>=0)
        ans=max(ans, map[y][x]+map[y][x+1]+map[y][x+2]+map[y-1][x+1]);
        
    if(x+1<M && y+2<N)
        ans=max(ans, map[y][x]+map[y+1][x]+map[y+2][x]+map[y+1][x+1]);
        
    if(y+2<N && x-1>=0)
        ans=max(ans, map[y][x]+map[y+1][x]+map[y+2][x]+map[y+1][x-1]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    
    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++)
            {
                exceptiondfs(j, i);
                visited[i][j]=true;
                dfs(j, i, map[j][i], 0);
                visited[i][j]=false;
            }

    cout<<ans;
}