( ext{Solution:})
好久没写啥(dfs)了，借这个题整理下细节。
观察到答案具有二分性，所以先求出其差的最大最小值，(log val)的复杂度不成问题。
考虑如何(check:)
考虑一个(dfs)预处理当前点为((i,j),)高度为(k)所能到达的所有点。这一步是(n^2)的复杂度。注意判断是否出界的时候符号不要打反，以及这题所谓高度差是在绝对值意义上的。
遍历变量时不要重名。之所以每次不需要清空(vis)是因为每次(dfs)都会保证找齐一个点所能到达的所有点。
于是，这题可以在(O(n^2log m))的复杂度完成。
还有一个想法是求出原树的最小生成树后处理出(siz)和子树的最大差。然后可以((n^2log n^2))实现这题。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+10;
int a[501][501],n;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
int L,R,ans,vis[501][501];
int dfs(int x,int y,int kk){
int cnt=1;
vis[x][y]=1;
for(int k=0;k<4;++k){
int nx=x+dx[k],ny=y+dy[k];
if(nx<1||ny<1||nx>n||ny>n||vis[nx][ny]||abs(a[x][y]-a[nx][ny])>kk)continue;
cnt+=dfs(nx,ny,kk);
}
return cnt;
}
bool check(int k){
memset(vis,0,sizeof vis);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
if(vis[i][j])continue;
int C=dfs(i,j,k);
if(C*2>=n*n)return true;
}
return false;
}
int main(){
scanf("%d",&n);
L=(1<<30);R=-L;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
for(int k=0;k<4;++k){
int x=i+dx[k],y=j+dy[k];
R=max(R,a[i][j]-a[x][y]);
L=min(L,a[i][j]-a[x][y]);
}
}
}
while(L<=R){
int mid=L+R>>1;
if(check(mid))ans=mid,R=mid-1;
else L=mid+1;
}
printf("%d
",ans);
return 0;
}