NOI 竞赛模拟题：最小体力消耗路径

题目描述

你准备去登山。给你一个 $m \times n$ 的整数矩阵 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。

你从左上角 (0, 0) 格子出发，目标是右下角 (m-1, n-1) 格子。你每次可以向 上、下、左、右 四个方向之一移动。

一条路径的 体力消耗 定义为：该路径中相邻格子之间 高度差绝对值 的 最大值 。

请你找出从左上角走到右下角的最小体力消耗值。

---

输入格式

第一行包含两个整数 $m$ 和 $n$，表示矩阵的行数和列数。 接下来 $m$ 行，每行包含 $n$ 个以空格分隔的整数，表示矩阵中各格子的高度。

输出格式

输出一个整数，表示最小体力消耗值。

---

输入输出样例

样例 1

输入：

3 3
1 2 2
3 8 2
5 3 5

输出：

2

解释：路径为 [1,3,5,3,5] ，高度差绝对值最大为 2 。

样例 2

输入：

3 3
1 2 3
3 8 4
5 3 5

输出：

1

解释：路径为 [1,2,3,4,5] ，相邻高度差最大均为 1 。

样例 3

输入：

5 1
1
2
3
4
5

输出：

1

---

数据范围与提示

• $m = heights.length$
• $n = heights[i].length$
• $1 \le m, n \le 100$
• $1 \le heights[i][j] \le 10^6$

---

1. 预备知识点

• 最短路算法（Dijkstra 变形）：普通的 Dijkstra 维护的是“路径和最小”，此题维护的是“路径最大边权最小”。
• 二分答案 + 搜索：对于“求最小的最大值”这类问题，二分搜索结果 $X$，判断是否能通过高度差 $\le X$ 的边到达终点。
• 并查集（Kruskal 思想）：将所有边按权值排序，依次加入，直到起点和终点连通。

---

2. 启发式思路引导（草稿纸上的推演）

第一步：题目特性分析

• 题目要求的是“路径上相邻格差的最大值”的“最小值”。
• 关键词：“最小化最大值”。
• 直觉：这通常指向 二分答案 或 Dijkstra 算法 的变体。

第二步：建模——将格子转化为图

• 每一个 (r, c) 是一个节点。
• 相邻两个格子之间有一条无向边，边权为 abs(h1 - h2)。
• 问题转化为：在图中找一条路径，使得路径上的最大边权最小。

第三步：二分答案思路

• 如果我们设定一个体力值上限 $X$：
  • 我们只能走权值 $\le X$ 的边。
  • 使用 BFS 或 DFS 判断能否从 (0, 0) 到达 (m-1, n-1)。
  • 如果能到达，说明 $X$ 可能还可以更小；反之需要增大 $X$。

第四步：Dijkstra 变体思路（本题推荐）

• 定义 dist[r][c] 为到达该格子的最小体力消耗。
• 初始化 dist 为正无穷，dist[0][0] = 0。
• 使用优先队列（小根堆）存储 {体力消耗, 行, 列}。
• 松弛操作：更新邻居的体力消耗为 max(当前点的体力消耗, 邻居与当前点的高度差)。

---

3. 算法逻辑流程图 (Mermaid)

本流程图展示 Dijkstra 算法 的实现逻辑。

graph TD
    A["开始: 初始化 dist 矩阵为无穷大"] --> B["设置 dist 0 0 为 0"]
    B --> C["将 (0, 0, 0) 加入优先队列 PQ"]
    C --> D{"PQ 是否为空?"}
    D -- "否" --> E["弹出 PQ 中体力消耗最小的点 (d, r, c)"]
    E --> F{"d 是否大于当前点的 dist 值?"}
    F -- "是 (失效状态)" --> D
    F -- "否" --> G["遍历 (r, c) 的 4 个邻居 (nr, nc)"]
    G --> H["计算边权 diff 为 abs(h_curr - h_neighbor)"]
    H --> I["计算新路径消耗 nd 等于 max(d, diff)"]
    I --> J{"nd 是否小于 dist nr nc?"}
    J -- "是" --> K["更新 dist nr nc 为 nd 并入队"]
    J -- "否" --> G
    K --> G
    G -- "邻居遍历完" --> D
    D -- "是" --> L["输出 dist m-1 n-1"]

---

4. 复杂度分析与优化建议

时间复杂度分析

• Dijkstra 方法：
  • 节点数为 $V = M \times N$，边数 $E \approx 4V$。
  • 复杂度为 $O(E \log V)$。在 $100 \times 100$ 规模下约为 $4 \times 10^4 \times 14 \approx 5.6 \times 10^5$，非常安全。
• 二分答案方法：
  • 二分范围 $10^6$，约 20 次循环。
  • 每次循环跑一次 $O(M \times N)$ 的 BFS。
  • 总复杂度 $O(MN \log(\text{max\_height}))$。同样能过。

空间复杂度优化

• dist 数组占用 $O(MN)$。
• 优先队列最坏情况存储所有边，占用 $O(MN)$。
• 总空间 $O(MN)$，约 40KB，远低于 NOI 256MB 的限制。

---

5. 读题关键词与坑点总结

1. “最小体力消耗”的定义：注意这不是路径之和，而是路径中单次跳跃的最大值。
2. 移动方向：明确是 4 方向，注意不要写成 8 方向（NOI 题目中经常互换）。
3. 数据范围：高度可达 $10^6$，体力消耗也可能达到 $10^6$，变量类型选择 int 即可，但初始化无穷大时要保证大于 $10^6$（推荐 0x3f3f3f3f）。
4. 起止点相同：虽然数据范围 $m, n \ge 1$，但习惯性考虑 $1 \times 1$ 矩阵的输出应为 0。
5. Dijkstra 优先队列比较函数：C++ priority_queue 默认是大根堆，需要自定义比较器或将权值取负以实现小根堆。