#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
using namespace std;
int n;
int mp[1024][1024],mpp[1024][1024];
int fa[1024][1024];
int num[1024],val[1024];
int top;
bool mark[1024][1024];int mark2[3000240][2];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int dp[3000860];
vector<int>edge[3000860];
void dfs(int x,int y)
{
    fa[x][y]=top;
    num[top]++;
    mark[x][y]=true;
    for(int i=0;i<4;i++)
    {
        int tx=x+dx[i],ty=y+dy[i];
        if(tx>0&&tx<=n&&ty>0&&ty<=n&&mark[tx][ty]==0&&mp[x][y]==mp[tx][ty])
            dfs(tx,ty);
    }
}
inline int max(int a,int b)
{
    return a>b?a:b;
}
void dfs2(int now,int nown,int nowmin,bool isfirst)
{
    //printf("dfs2(%d,%d,%d,%d)\n",now,nown,nowmin,isfirst);
    if(dp[nown]>nowmin)
        dp[nown]=nowmin;
    mark2[now][isfirst]++;
    for(int i=0;i<edge[now].size();i++)
    {
        int u=edge[now][i];
        if(mark2[u][0]<top)
            dfs2(u,nown+val[u],max(nowmin,abs(val[now]-val[u])),false);
        if(isfirst&& mark2[u][1]<top)
            dfs2(u,num[u],0,true);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&mp[i][j]);
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(!mark[i][j])
                dfs(i,j),val[top]=mp[i][j],top++;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=0;k<4;k++)
            {
                int tx=i+dx[k],ty=j+dy[k];
                if(tx>0&&tx<=n&&ty>0&&ty<=n&&mp[i][j]!=mp[tx][ty])
                    edge[fa[i][j]].push_back(fa[tx][ty]),edge[fa[tx][ty]].push_back(fa[i][j]);
            }
    /*for(int i=0;i<top;i++)
    {
        printf("group %d:val=%d,num=%d\n    topoint:",i,val[i],num[i]);
        for(int j=0;j<edge[i].size();j++)
            printf("%d ",edge[i][j]);
        printf("\n");
    }*/
    dfs2(0,num[1],0,true);
    int minn=2147483647;
    for(int i=(n*n+1)/2;i<=n*n;/*printf("dp[%d]=%d\n",i,dp[i]),*/i++)
        if(minn>dp[i])
            minn=dp[i];
    printf("%d",minn);
    return 0;
}

1AC，1WA，8RE 哪位大佬帮忙改改