题意是从地图的左上角走到右下角，求所走的路径中最大值和最小值的差值，输出最小的差值。先用二分去找差值，然后枚举区间，看能不能从左上角走到右下角，最后的下界即为所求。
AC代码：
#include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; struct Node{ int x,y; }Now,S,Next; int vis[105][105]; int MAP[105][105]; int dir[4][2] = {1,0,0,1,-1,0,0,-1}; int n; bool in(int x,int y,int low,int high){ if(x>=0&&y>=0&&x<n&&y<n&&!vis[x][y]&&MAP[x][y]>=low&&MAP[x][y]<=high)return true; return false; } bool bfs(int low,int high){ memset(vis,0,sizeof(vis)); S.x = 0; S.y = 0; queue<Node> q; if(MAP[0][0]<low || MAP[0][0]>high)return false; vis[0][0] = 1; while(!q.empty())q.pop(); q.push(S); while(!q.empty()){ Now = q.front(); q.pop(); if(Now.x == n-1 && Now.y == n-1)return true; for(int i=0;i<4;i++){ Next.x = Now.x + dir[i][0]; Next.y = Now.y + dir[i][1]; if(in(Next.x,Next.y,low,high)){ vis[Next.x][Next.y] = 1; q.push(Next); } } } return false; } bool Check(int x){ for(int i=0;i<=110;i++){ if(bfs(i,i+x))return true; } return false; } int main() { scanf("%d",&n); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ scanf("%d",&MAP[i][j]); } } int sum = 0; int l=0,r=110;int mid; while(l <= r){ mid = (l + r) / 2; if(Check(mid)){ r = mid - 1; } else l = mid + 1; } printf("%d\n",l); return 0; }