题意分析

农夫约翰和奶牛贝西需要从山地地图的左上角（起点 $(1,1)$）走到右下角（终点 $(n,n)$），移动方式仅限于上下左右（不能走对角线）。他们的目标是找到一条路径，使得该路径上的最高海拔与最低海拔的差值最小，并输出这个最小差值。

输入与约束

• 地图大小：$N \times N$（$2 \leq N \leq 100$）
• 海拔范围：$0 \leq \text{海拔} \leq 110$
• 移动方式：只能向上、下、左、右移动

输出要求

• 输出最优路径上的最小高度差（即路径上的最大值减去最小值的最小可能值）。

解题思路

本题的关键在于如何高效地找到满足条件的最小高度差。直接枚举所有路径显然不可行（时间复杂度太高），因此我们需要采用更优化的方法。

核心思路：二分答案 + BFS验证

1. 二分搜索最小高度差

   • 可能的差值范围是 $[0, 110]$（因为海拔范围是 $0$ 到 $110$）。
   • 使用二分法来猜测最小差值 $mid$，并验证是否存在一条路径，其最高和最低海拔的差值不超过 $mid$。

2. 验证是否存在可行路径（BFS）

   • 对于当前猜测的差值 $mid$，枚举所有可能的最低海拔 $l$，并计算对应的最高海拔 $r = l + mid$。
   • 使用 BFS 检查是否存在一条路径，使得路径上的所有海拔都在 $[l, r]$ 范围内。
   • 如果能找到这样的路径，说明 $mid$ 是一个可行解，尝试寻找更小的差值；否则，调整二分范围。

算法流程

1. 初始化：读取地图数据。
2. 二分搜索：在 $[0, 110]$ 范围内二分最小差值 $mid$。
3. 验证 $mid$ 是否可行：
   • 遍历所有可能的 $l$（最低海拔），计算 $r = l + mid$。
   • 使用 BFS 检查是否存在一条从 $(1,1)$ 到 $(n,n)$ 的路径，路径上的海拔均在 $[l, r]$ 之间。
4. 输出结果：最终找到的最小差值。

标程

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=105;
 
int n;
int ma[MAXN][MAXN], vis[MAXN][MAXN];
int dx[4]={1,0,-1,0};  // 方向数组：下、右、上、左
int dy[4]={0,1,0,-1};
 
// BFS 检查是否存在路径，路径上的海拔在 [l, r] 之间
bool bfs(int l, int r) {
    if(ma[1][1] < l || ma[1][1] > r) return false;  // 起点不满足条件
    queue<pair<int,int>> q;
    q.push(make_pair(1,1));
    vis[1][1] = 1;
    while(!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for(int i=0; i<4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if(!vis[nx][ny] && nx > 0 && nx <= n && ny > 0 && ny <= n) {
                vis[nx][ny] = 1;
                if(ma[nx][ny] >= l && ma[nx][ny] <= r) {
                    q.push(make_pair(nx, ny));
                    if(nx == n && ny == n) return true;  // 到达终点
                }
            }
        }
    }
    return false;
}
 
// 检查是否存在差值不超过 mid 的路径
bool check(int mid) {
    for(int l=0; l + mid <= 110; ++l) {  // 枚举最低海拔 l
        memset(vis, 0, sizeof(vis));     // 重置访问标记
        if(bfs(l, l + mid)) return true; // 存在可行路径
    }
    return false;
}
 
int main() {
    scanf("%d", &n);
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
            scanf("%d", &ma[i][j]);
    // 二分搜索最小差值
    int l=0, r=110;
    while(l < r) {
        int mid = (l + r) >> 1;  // 取中间值
        if(check(mid)) r = mid;   // 可以更小
        else l = mid + 1;         // 需要增大
    }
    cout << r;  // 输出最小差值
    return 0;
}