M30909: 最优爬山路径

binary search, bfs, http://cs101.openjudge.cn/practice/30909/

小P要从一块山地的一头走到另一头。山地可以看作是一个由n×m个单元构成的网格，每个单元有一个高度值。小P要从左上角的单元走到右下角的单元。小P只能沿着东西南北四个方向走。小P有恐高症，又讨厌爬升，所以他想要找一条路，使得路上高度差的绝对值最大的相邻两个单元格的高度差的绝对值H尽可能小。问H最小可以是多少。
输入
第1行是整数n和m,表示山地是一个n×m的网格( 1 < n,m <= 100) 接下来有n行，每行有m个整数，描述了山地中所有单元的高度h。（0 <= h <= 10000)
输出
最小的H
样例输入
3 3
1 3 8
2 1 5
4 6 3
样例输出
3

这个问题可以通过二分查找（Binary Search）结合广度优先搜索（BFS）来解决。

解题思路

二分查找高度差 $H$ ：
- 最小可能的高度差 $H$ 为 $0$ ，最大可能的高度差为网格中最大高度与最小高度之差（不超过 $10000$ ）。
- 我们可以对高度差 $H$ 的范围进行二分查找。
BFS 验证可行性：
- 对于每次二分选择的中间值 mid，我们需要判断是否存在一条从左上角 (0, 0) 到右下角 (n-1, m-1) 的路径，使得路径上任意相邻两个单元格的高度差的绝对值都不超过 mid。
- 这个验证过程可以使用 BFS（或 DFS）来实现。我们从 (0, 0) 开始，只向高度差不超过 mid 且未访问过的相邻格子移动。如果最终能到达 (n-1, m-1)，说明当前的 mid 是可行的。
调整二分区间：
- 如果当前 mid 可行，尝试寻找更小的 $H$ ，即在左半区间继续查找（high = mid - 1），并记录当前可行解。
- 如果不可行，说明限制太小，需要增加 $H$ ，在右半区间继续查找（low = mid + 1）。

Python 3 实现代码

python

import sys
from collections import deque


def solve():
    # 读取所有输入数据
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    n = int(input_data[0])
    m = int(input_data[1])

    grid = []
    idx = 2
    for _ in range(n):
        grid.append([int(x) for x in input_data[idx : idx + m]])
        idx += m

    # BFS 函数：验证在最大高度差限制为 H 的情况下，能否从起点走到终点
    def can_reach(H):
        visited = [[False] * m for _ in range(n)]
        queue = deque([(0, 0)])
        visited[0][0] = True

        # 四个移动方向：上下左右
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        while queue:
            r, c = queue.popleft()

            # 成功到达终点
            if r == n - 1 and c == m - 1:
                return True

            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < m:
                    if not visited[nr][nc]:
                        # 检查高度差是否在限制 H 以内
                        if abs(grid[r][c] - grid[nr][nc]) <= H:
                            visited[nr][nc] = True
                            queue.append((nr, nc))
        return False

    # 确定二分查找的上下边界
    flat_grid = [val for row in grid for val in row]
    min_val = min(flat_grid)
    max_val = max(flat_grid)

    low = 0
    high = max_val - min_val
    ans = high

    # 二分查找
    while low <= high:
        mid = (low + high) // 2
        if can_reach(mid):
            ans = mid
            high = mid - 1  # 尝试寻找更小的可行高度差
        else:
            low = mid + 1  # 限制太小，增加高度差

    print(ans)


if __name__ == "__main__":
    solve()

复杂度分析

时间复杂度： 二分查找的范围为 $[0, 10000]$ ，最多需要进行 $\log_{2} (10000) \approx 14$ 次迭代。在每次迭代中，BFS 最多遍历网格中的所有节点和边，时间复杂度为 $O (V + E)$ ，其中节点数 $V = n \times m \leq 10000$ ，边数 $E \approx 4 \times n \times m$ 。因此，整体时间复杂度为 $O (n \times m \log (max_h e i g h t))$ 。对于 $100 \times 100$ 的网格，运算次数大约为 $14 \times 10000 \approx 1.4 \times 10^{5}$ ，在 Python 中可以在 100ms 内轻松完成，远低于 1000ms 的限制。
空间复杂度： 主要开销为存储网格的 grid 数组、BFS 使用的 visited 数组以及队列，最大空间占用大约为 $O (n \times m)$ 。在 $100 \times 100$ 规模下，占用内存极小，安全符合 65536kB 的内存限制。

M30909: 最优爬山路径 ​

M30909: 最优爬山路径