T28972: 海拔

binary, bfs, Dijkstra, http://cs101.openjudge.cn/practice/28972

一片矩形地域被横平竖直地切分成了 n × m 片方形区块. 其中位于第 i 行第 j 列的区块的平均海拔是 hi, j.

某人要从第 1 行第 1 列的区块移动至第 n 行第 m 列的区块. 每次移动时, 她只能选择一个与当前所处区块有公共边的相邻区块, 并移动至该区块.

跨越处于不同海拔的区块是相当耗费体力的. 定义一次移动的体力消耗值为该次移动涉及到的两个区块的海拔之差, 某人希望你能够帮助她找到一条能顺利抵达目的地的路径, 使得所有移动中体力消耗值的最大值尽可能小.

输入

输入数据的第一行包含两个正整数 n, m, 表示矩形地域的大小. 接下来 n 行, 每行 m 个数, 第 i 行第 j 个正整数 h[i][j] 表示位于第 i 行第 j 列的区块的平均海拔. 1 ≤ n, m, ≤ 400, 1≤ hi,j ≤ 10^9.

输出

输出一行一个非负整数表示最优情况下的体力消耗的最大值.

样例输入

4 5
5 3 3 7 9
5 5 4 2 8
9 1 1 7 10
9 8 10 1 7

样例输出

4

提示

bfs

来源

2024-TA-xjk

这个问题可以转化为图论中的最小瓶颈路径问题（Minimax Path Problem），其解法通常有三种：

1. 并查集 + 排序 (Kruskal 思想)：最直观。

2. 二分答案 + BFS/DFS：二分一个体力消耗值 midmid，只走差值 ≤mid≤mid 的路，看能不能到终点。

3. 改进的 Dijkstra：将 Dijkstra 的松弛操作 dist[v] = min(dist[v], dist[u] + weight) 改为 dist[v] = min(dist[v], max(dist[u], weight))。

并查集 + 排序 (Kruskal 思想)思路

1. 问题分析：我们需要找到一条从起点 $(1,1)$ 到终点 $(n,m)$ 的路径，使得路径上所有相邻格点海拔差的最大值最小。这非常符合最小生成树（MST）的特性。
2. 建模：
   • 将每个区块看作图中的一个节点。
   • 相邻（上下左右）的区块之间存在一条边，边的权重为这两个区块海拔差的绝对值。
   • 我们的目标是找到一条路径，使得路径上的最大边权最小。
3. 算法选择：
   • Kruskal 算法思想：将所有边按权重从小到大排序。依次将边加入图中，并使用并查集（Union-Find）维护连通性。当我们加入某条边后，起点 $(1,1)$ 和终点 $(n,m)$ 变得连通，那么这条边的权重就是我们要找的答案。
   • 为什么可行：因为我们是按权重从小到大加边的，所以第一次让起点和终点连通的那条边，一定是所有可行路径中“最大边权”最小的那一个。

Python 代码实现。考虑到 Python 的执行效率和 64MB 的内存限制，我们需要注意内存管理（如避免存储多余的列表）和使用高效的输入输出。

import sys
from operator import itemgetter

def solve():
    # 使用生成器逐个读取输入，节省内存
    def get_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    
    tokens = get_tokens()
    
    try:
        n = int(next(tokens))
        m = int(next(tokens))
    except (StopIteration, ValueError):
        return
    
    size = n * m
    # 特判：如果只有一个区块，海拔差最大值为0
    if size <= 1:
        if size == 1:
            print(0)
        return

    # 读取所有海拔高度，存储在扁平化的1D列表中
    h = [0] * size
    for i in range(size):
        h[i] = int(next(tokens))
    
    # 构造所有的边 (权重, 点u, 点v)
    edges = []
    for r in range(n):
        offset = r * m
        for c in range(m):
            u = offset + c
            # 添加向右的边
            if c + 1 < m:
                v = u + 1
                diff = h[u] - h[v]
                edges.append((diff if diff >= 0 else -diff, u, v))
            # 添加向下的边
            if r + 1 < n:
                v = u + m
                diff = h[u] - h[v]
                edges.append((diff if diff >= 0 else -diff, u, v))
    
    # 释放海拔列表以节省内存
    h = None
    
    # 按权重从小到大排序
    edges.sort(key=itemgetter(0))
    
    # 并查集初始化
    parent = list(range(size))
    
    # 路径压缩的并查集查找函数
    def find(i):
        root = i
        while parent[root] != root:
            root = parent[root]
        curr = i
        while parent[curr] != root:
            # 路径压缩：直接指向根节点
            parent[curr], curr = root, parent[curr]
        return root

    start_node = 0
    end_node = size - 1
    
    # 依次加入边，直到起点和终点连通
    for diff, u, v in edges:
        root_u = find(u)
        root_v = find(v)
        
        if root_u != root_v:
            parent[root_u] = root_v
            # 检查起点(0,0)和终点(n-1,m-1)是否连通
            if find(start_node) == find(end_node):
                print(diff)
                return

if __name__ == "__main__":
    solve()

关键点解释

1. 内存优化：
   • 题目限制为 64MB。在 Python 中，每个整数和元组都是对象，会占用较多内存。通过 h = None 手动释放不再需要的列表，并使用 sys.stdin 迭代读取，可以有效控制内存峰值。
   • 使用 1D 数组 h[r * m + c] 代替 2D 数组可以减少索引开销和嵌套列表带来的内存开销。
2. 效率优化：
   • 使用 operator.itemgetter(0) 排序比 lambda 函数快。
   • 并查集的路径压缩（Path Compression）将 find 操作的时间复杂度降低到近乎常数 $O(\alpha (V))$。
   • Kruskal 算法复杂度为 $O(E\log E)$，其中 $E$ 是边数（约 $2\times 400\times 400=320,000$），在 2 秒的时间限制内绰绰有余。
3. 海拔差处理：
   • diff if diff >= 0 else -diff 比 abs(diff) 略快一些。

二分答案 + BFS思路

1. 问题转化：我们不直接寻找路径，而是反过来思考：是否存在一条从 (0, 0) 到 (n-1, m-1) 的路径，其路径上所有相邻区块的海拔差的最大值不超过 D？
2. 二分查找：我们对 D 的可能值进行二分查找。D 的最小值是 0（所有区块海拔相同），最大值是地图上最高海拔与最低海拔之差。
   • 对于一个给定的 D，我们可以通过 BFS 来验证是否存在满足条件的路径。
   • 如果 BFS 成功找到了路径，说明 D 是一个可行解，我们可以尝试寻找一个更小的 D。
   • 如果 BFS 失败，说明 D 太小了，我们需要尝试一个更大的 D。
3. BFS 验证：在每次验证中，BFS 的规则如下：
   • 从起点 (0, 0) 开始。
   • 对于当前所在的区块 (i, j)，我们检查它的四个邻居。
   • 如果邻居 (ni, nj) 没有被访问过，并且 abs(h[ni][nj] - h[i][j]) <= D，那么就可以从 (i, j)移动到 (ni, nj)。我们将 (ni, nj) 加入队列，并标记为已访问。
   • 如果在 BFS 过程中到达了终点 (n-1, m-1)，则说明在当前 D 值下存在合法路径。

这种方法将一个最优化问题转化为了一个判定问题，通过二分查找高效地找到满足条件的最小 D。

Python 代码实现

from collections import deque
import sys


def main():
    data = sys.stdin.read().split()
    if not data:
        return

    n = int(data[0])
    m = int(data[1])
    h = []
    index = 2
    for i in range(n):
        row = list(map(int, data[index:index + m]))
        h.append(row)
        index += m

    # 边界情况
    if n == 1 and m == 1:
        print(0)
        return

    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    # BFS 验证函数
    def canReach(limit):
        visited = [[False] * m for _ in range(n)]
        q = deque()
        q.append((0, 0))
        visited[0][0] = True

        while q:
            x, y = q.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                    diff = abs(h[nx][ny] - h[x][y])
                    if diff <= limit:
                        if nx == n - 1 and ny == m - 1:
                            return True
                        visited[nx][ny] = True
                        q.append((nx, ny))
        return False

    all_vals = [h[i][j] for i in range(n) for j in range(m)]
    low = 0
    high = max(all_vals) - min(all_vals) + 1

    ans = high - 1 # 初始化为最大可能值
    while low < high:
        mid = (low + high) // 2
        if canReach(mid):
            high = mid
            ans = mid
        else:
            low = mid + 1

    print(ans)


if __name__ == "__main__":
    main()

改进的 Dijkstra思路

将 Dijkstra 的松弛操作 dist[v] = min(dist[v], dist[u] + weight) 改为 dist[v] = min(dist[v], max(dist[u], weight))。

使用 Dijkstra 算法来解决这个问题，核心思想是将 “最大体力消耗” 当作路径的 “权重”，然后寻找从起点到终点的 “最短路径”，其中路径的 “长度” 定义为路径上所有边（相邻区块海拔差）的最大值。

算法思路

1. 图的构建：我们将每个区块 (i, j) 视为图中的一个节点。
2. 边的权重：对于每个节点 (i, j)，它与四个相邻节点（上、下、左、右）之间的边的权重，定义为这两个区块海拔高度的差值（取绝对值）。
3. Dijkstra 算法的适配：
   • 我们维护一个 dist 矩阵，其中 dist[i][j] 表示从起点 (0, 0) 到节点 (i, j) 的路径上，最大的体力消耗值。
   • 算法的目标是找到 dist[n-1][m-1]，即从起点到终点的所有可能路径中，那个最小的 “最大体力消耗值”。
   • 我们使用一个优先队列（最小堆）来总是选择当前 dist 值最小的节点进行扩展。这是因为，一旦我们通过这种方式到达了终点，就可以立即返回结果，因为 Dijkstra 算法保证了这是最优解。

Python 代码实现

import sys
import heapq

def main():
    n, m = map(int, sys.stdin.readline().split())
    h = []
    for _ in range(n):
        row = list(map(int, sys.stdin.readline().split()))
        h.append(row)

    # 方向向量：上、下、左、右
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # 初始化距离矩阵，所有值设为无穷大
    INF = float('inf')
    dist = [[INF for _ in range(m)] for _ in range(n)]
    dist[0][0] = 0 # 起点到自身的最大消耗为0

    # 优先队列 (当前最大消耗, i, j)，初始加入起点
    heap = []
    heapq.heappush(heap, (0, 0, 0))

    while heap:
        # 取出当前路径最大消耗最小的节点
        current_max, i, j = heapq.heappop(heap)

        # 关键优化：如果当前弹出的消耗大于已知的最小消耗，则跳过
        if current_max > dist[i][j]:
            continue

        # 如果到达终点，直接返回结果
        if i == n - 1 and j == m - 1:
            print(current_max)
            return

        # 探索四个方向的邻居
        for di, dj in directions:
            ni, nj = i + di, j + dj
            if 0 <= ni < n and 0 <= nj < m:
                # 计算移动到邻居的体力消耗
                cost = abs(h[ni][nj] - h[i][j])
                # 新路径的最大消耗是当前路径最大消耗和本次移动消耗中的较大者
                new_max = max(current_max, cost)
                
                # 如果新路径的最大消耗更小，则更新并加入堆
                if new_max < dist[ni][nj]:
                    dist[ni][nj] = new_max
                    heapq.heappush(heap, (new_max, ni, nj))
    
    # 理论上不会到达这里，因为题目保证有路径
    print(-1)

if __name__ == "__main__":
    main()

代码解析

1. 初始化：
   • dist 矩阵被初始化为无穷大（INF），表示初始时我们不知道如何到达任何节点。
   • 起点 (0, 0) 的 dist 值被设为 0，因为从起点到自己不需要移动，消耗为 0。
   • 优先队列 heap 被初始化，并放入起点 (0, 0, 0)，其中第一个 0 是 dist 值。
2. 主循环：
   • 我们不断从优先队列中弹出 dist 值最小的节点 (current_max, i, j)。
   • 优化判断：if current_max > dist[i][j]: continue。这是 Dijkstra 算法中一个至关重要的优化。因为一个节点可能会被多次加入堆中（带着不同的 current_max 值）。当我们弹出一个节点时，如果它记录的 current_max 已经大于我们已知的、到达该节点的最小 dist 值，说明这个条目已经过时，我们可以直接忽略它，从而节省大量计算。
   • 终点判断：当我们弹出的节点正好是终点 (n-1, m-1) 时，我们可以立即打印并返回 current_max。这是因为 Dijkstra 算法的特性保证了，通过优先队列弹出的第一个到达终点的路径，一定是 “最短” 的路径（即最大消耗最小的路径）。
3. 邻居探索：
   • 对于当前节点 (i, j)，我们检查它的四个邻居 (ni, nj)。
   • cost 是移动到邻居的体力消耗。
   • new_max 是到达邻居节点的新路径的最大消耗。它等于 “到达当前节点的最大消耗” 和 “当前移动的消耗” 这两者中的较大者。
   • 如果 new_max 比我们已知的到达邻居节点的最小消耗 dist[ni][nj] 还要小，那就意味着我们找到了一条更好的路径。于是，我们更新 dist[ni][nj] 的值，并将这个新的状态 (new_max, ni, nj) 加入优先队列，供后续探索。

复杂度分析

• 每个节点最多会被加入优先队列 O(1) 次（由于 heapq 的特性和 dist 矩阵的保护）。
• 每次 heappush 或 heappop 操作的时间复杂度是 O(log(nm))。
• 因此，总的时间复杂度大约是 O(nm log(nm))。对于 n, m <= 400 的情况，nm 大约是 160,000，log(nm) 大约是 18，所以总操作数大约是 2.88 * 10^6，这在 Python 中是可以在时间限制内通过的。

虽然理论上二分 + BFS 的复杂度 O(nm log(max_h)) 通常更优（因为 log(max_h) 通常比 log(nm)小），但 Dijkstra 算法的实现直观地体现了问题的 “最短路径” 本质，也是一种非常强大且正确的解法。

Q：这是Dijkstra变形，不是常规的：# 计算移动到邻居的体力消耗。

你提出了一个非常好的观察！

你说得对，在这个问题中，我们对 Dijkstra 算法进行了变形，以适应 “最小化路径上最大边权” 这一特殊需求。

常规 Dijkstra 算法

在常规的 Dijkstra 算法中，路径的总成本是路径上所有边权的总和。

• 当我们从节点 u 移动到节点 v 时，新的路径成本是 dist[u] + weight(u, v)。
• 我们的目标是找到从起点到终点的总成本最小的路径。

变形后的 Dijkstra 算法（用于此问题）

在这个问题中，路径的 “成本” 被定义为路径上所有边权的最大值。

• 当我们从节点 (i, j) 移动到节点 (ni, nj) 时，这次移动的消耗是 cost = abs(h[ni][nj] - h[i][j])。
• 新路径的 “成本”（即最大消耗）是 new_max = max(current_max, cost)。这里的 current_max 是到达 (i, j) 的路径上的最大消耗。
• 我们的目标是找到从起点到终点的最大边权最小的路径。

为什么这个变形是正确的？

这个变形的正确性源于问题的核心要求。我们并不关心路径上所有消耗的总和，只关心其中最 “费力” 的那一步。

• 路径表示：dist[i][j] 不再表示到 (i, j) 的总消耗，而是表示到 (i, j) 的最小可能的最大消耗。
• 松弛操作：当我们考虑通过 (i, j) 到达 (ni, nj) 时，新的路径的最大消耗是 max(dist[i][j], cost)。如果这个新的最大值比我们已知的 dist[ni][nj] 更小，那么这就是一条更优的路径，我们就应该更新 dist[ni][nj] 并将其加入优先队列。

与常规 Dijkstra 的核心区别

特性	常规 Dijkstra 算法	变形后的 Dijkstra 算法 (本题)
路径成本定义	路径上所有边权的 总和	路径上所有边权的 最大值
松弛操作	new_cost = dist[u] + weight(u, v)	new_max = max(dist[u], weight(u, v))
优先队列排序依据	路径的 总消耗	路径的 最大消耗

总结

虽然算法的框架（使用优先队列、贪心选择、松弛操作）保持不变，但路径成本的定义和计算方式发生了根本变化。

这个变形后的 Dijkstra 算法专门用于解决最小瓶颈路径问题（Minimum Bottleneck Path Problem）。在一个边权非负的图中，从起点到终点的最小瓶颈路径，其瓶颈（最大边权）等于通过这种变形的 Dijkstra 算法计算出的 dist[end] 值。

所以，你的理解是完全正确的，这确实是一个基于 Dijkstra 思想的聪明变形，而不是标准的求和版本。