分析
看到题目所求的是一个最大差值，很快想到二分答案，对于一个二分到的 \(mid\)，我们枚举满足要求的最小值和最大值，表示我们路径只能经过权值在二者之间的点，这样走一个 \(dfs\)，用 \(vis\) 数组判断起点终点是否连通就可以了。
这样二分的正确性也容易证明了，当一个答案可行时，更大的答案只会增加可行的点的位置，所以满足二分答案的性质，这样此题就解决了。
代码（将枚举放在前面，效果是一样的）
#include<bits/stdc++.h>
using namespace std;
inline void read(int &res){
char c;
int f=1;
res=0;
c=getchar();
while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
while(c>=‘0‘&&c<=‘9‘)res=(res<<1)+(res<<3)+c-48,c=getchar();
res*=f;
}
int n;
int mp[105][105];
int vis[105][105];
int ans=1e9;
void dfs(int x,int y,int l,int r){
if(mp[x][y]>r||mp[x][y]<l)return;//不满足范围
if(vis[x][y])return;//到达过
vis[x][y]=1;
dfs(x+1,y,l,r);
dfs(x-1,y,l,r);
dfs(x,y+1,l,r);
dfs(x,y-1,l,r);
return;
}
int main()
{
read(n);
for(int i=0;i<=n;i++)mp[i][0]=mp[i][n+1]=mp[0][i]=mp[n+1][i]=-1;//处理边界
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
read(mp[i][j]);
}
}
for(int i=0;i<=110;i++){//枚举最小值
int l=i,r=110;//二分答案
while(l<=r){
int mid=(l+r)>>1;
memset(vis,0,sizeof(vis));
dfs(1,1,i,mid);
if(vis[n][n]){
ans=min(ans,mid-i);
r=mid-1;
}
else l=mid+1;
}
}
cout<<ans;
return 0;
}