题意：输入N，给你一个N*N的海拔地图，让你找一条从左上角到右下角的路。要求该条路上的最高海拔 - 最低海拔值最小，输出这个值。
思路：暴力DFS搜索所有路，路上维护最高和最低海拔，求一个最小值就是答案，但是时间复杂度太高。我们可以考虑二分求一个这个差值，然后判断看能否找到一条左上角到右下角的路，但是这样只能用DFS，只有这个差的话DFS还是会超时。我们有了这个差值，我们在枚举最小海拔，然后在这个区间才可以走，这样DFS就可以了，也满足BFS的条件每个点只访问一次。
注意第一个点要在枚举的这个范围之内，容易漏这个条件。
//#include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int MAXN = 505; const int INF = 0x3f3f3f3f; int n, a[MAXN][MAXN]; struct Node { int x, y; }NEXT; bool vis[MAXN][MAXN]; bool BFS(int low, int up) { if (a[0][0] < low || a[0][0] > up) return false; int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; memset(vis, 0, sizeof(vis)); vis[0][0] = true; queue<Node> Q; Node NOW; NOW.x = 0, NOW.y = 0; Q.push(NOW); while (!Q.empty()) { Node u = Q.front(); Q.pop(); if (u.x == n-1 && u.y == n-1) return true; for (int i = 0; i < 4; i++) { int X = u.x + dir[i][0], Y = u.y + dir[i][1]; if (X >= 0 && Y >= 0 && X < n && Y < n && !vis[X][Y] && a[X][Y] >= low && a[X][Y] <= up) { vis[X][Y] = true; NEXT.x = X, NEXT.y = Y; Q.push(NEXT); } } } return false; } bool check(int m) { for (int i = 0; i+m <= 110; i++) { if (BFS(i, i+m)) return true; } return false; } int main() { while (~scanf("%d", &n)) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { scanf("%d", &a[i][j]); } } int l = 0, r = 110, m = l + (r - l) / 2; while (l < r) { if (check(m)) r = m; else l = m + 1; m = l + (r - l) / 2; } cout << l << endl; } return 0; } /* 5 1 1 3 6 8 1 2 2 5 5 4 4 0 3 3 8 0 2 3 4 4 3 0 2 1 */