用 Python 编写程序，查找到达目的地所需增加的最小高度数

pythonserver side programmingprogramming更新于 2026/1/15 3:24:17

假设我们有一个矩阵 M，其中 M[r][c] 表示该单元格的高度。如果我们当前位于左上角，想要前往右下角。只有当相邻单元格的高度小于或等于当前单元格的高度时，我们才能移动到相邻单元格(上、下、左、右)。我们可以在移动之前增加任意数量的单元格的高度，因此我们必须找到需要增加的最小总高度，以便我们可以转到右下角的单元格。

因此，如果输入如下

2	4	5
8	6	1

那么输出将是 4，因为我们可以采用以下路径 [2, 4, 5, 1] 并将高度更改为此配置 −

5	5	5
8	6	1

为了解决这个问题，我们将遵循以下步骤 −

INF := 无穷大

R, C := 矩阵的行数，矩阵的列数
pq := 使用堆创建一个优先级队列，并将 [0, R-1, C-1, M[-1, -1]] 插入其中
dist := 一个映射
dist[R-1, C-1, A[-1, -1]] := 0
当 pq 不为空时，执行
- 从 pq 中删除一个元素并将其存储到 d、r、c、h 中
- 如果 dist[r, c, h] < d，然后
  - 进行下一次迭代
- 如果 r 和 c 均为 0，则
  - 返回 d
- 对于 [[r+1, c], [r, c+1], [r-1, c], [r, c-1]] 中的每一对 (nr, nc)，执行
  - 如果 0 <= nr < R 且 0 <= nc < C，则
    - 如果 d2 < dist[nr, nc, h2]，然后
      - dist[nr, nc, h2] := d2
      - 将 [d2, nr, nc, h2] 插入 pq

让我们看看下面的实现以便更好地理解 −

示例

import collections
import heapq
class Solution:
   def solve(self, A):
      INF = float('inf')
      R, C = len(A), len(A[0])

      pq = [[0, R-1, C-1, A[-1][-1]]]
      dist = collections.defaultdict(lambda: INF)
      dist[R-1, C-1, A[-1][-1]] = 0
      while pq:
         d, r, c, h = heapq.heappop(pq)
         if dist[r, c, h] < d:
            continue
         if r == c == 0:
            return d
         for nr, nc in [[r+1, c], [r, c+1], [r-1, c], [r, c-1]]:
            if 0 <= nr < R and 0 <= nc < C:
               h2 = max(A[nr][nc], h)
               d2 = d + max(h2 - A[nr][nc], 0)
               if d2 < dist[nr, nc, h2]:
                  dist[nr, nc, h2] = d2
                  heapq.heappush(pq, [d2, nr, nc, h2])
ob = Solution()
matrix = [
[2, 4, 5],
[8, 6, 1]
]
print(ob.solve(matrix))