昨天看到这个题还以为是个脑残的dp， 然而脑残的是我。
题目意思就是从左上角走到右下角， 设x为路径上的最大值-最小值， 求x的最小值。
二分x， 对于每一个x， 枚举下界lower， lower从0开始枚举， 每一次bfs的时候， 如果一个点的值小于lower或者大于lower+x， 那么就不走这个点， 看最后能否走到终点。
自己的整数二分写的真是不忍直视...改了好久。
ps：poj2922貌似和这个一样
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define pb(x) push_back(x) 4 #define ll long long 5 #define mk(x, y) make_pair(x, y) 6 #define lson l, m, rt<<1 7 #define mem(a) memset(a, 0, sizeof(a)) 8 #define rson m+1, r, rt<<1|1 9 #define mem1(a) memset(a, -1, sizeof(a)) 10 #define mem2(a) memset(a, 0x3f, sizeof(a)) 11 #define rep(i, a, n) for(int i = a; i<n; i++) 12 #define ull unsigned long long 13 typedef pair<int, int> pll; 14 const double PI = acos(-1.0); 15 const double eps = 1e-8; 16 const int mod = 1e9+7; 17 const int inf = 1061109567; 18 const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; 19 int a[150][150], vis[120][120], n; 20 int bin(int lower, int upper) { 21 queue <pll> q; 22 mem(vis); 23 if(a[0][0]<lower||a[0][0]>upper) 24 return 0; 25 q.push(mk(0, 0)); 26 vis[0][0] = 1; 27 while(!q.empty()) { 28 pll tmp = q.front(); q.pop(); 29 int x = tmp.first; 30 int y = tmp.second; 31 if(x == n-1 && y == n-1) 32 return 1; 33 for(int i = 0; i<4; i++) { 34 int tmpx = x+dir[i][0]; 35 int tmpy = y+dir[i][1]; 36 if(tmpx>=0&&tmpx<n&&tmpy>=0&&tmpy<n&&!vis[tmpx][tmpy]) { 37 vis[tmpx][tmpy] = 1; 38 if(a[tmpx][tmpy]<=upper&&a[tmpx][tmpy]>=lower) 39 q.push(mk(tmpx, tmpy)); 40 } 41 } 42 } 43 return 0; 44 } 45 int check(int val) { 46 for(int i = 0; i+val<=110; i++) { 47 if(bin(i, i+val)) 48 return 1; 49 } 50 return 0; 51 } 52 int main() 53 { 54 while(cin>>n) { 55 for(int i = 0; i<n; i++) { 56 for(int j = 0; j<n; j++) { 57 scanf("%d", &a[i][j]); 58 } 59 } 60 int l = 0, r = 110; 61 while(r>l) { 62 int m = l+r>>1; 63 if(check(m)) { 64 r = m; 65 } else { 66 l = m+1; 67 } 68 } 69 cout<<l<<endl; 70 } 71 }