程序查找要增加高度以到达Python中的目标的最小高度

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

所以，如果输入像

然后输出将为4，因为我们可以采用以下路径[2，4，5，1]并将高度更改为此配置-

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

INF：=无穷大

• R，C：=矩阵的行数，矩阵的列数

• pq：=使用堆创建优先级队列，然后将[0，R-1，C-1，M [-1，-1]]插入其中

• dist：=映射

• dist [R-1，C-1，A [-1，-1]]：= 0

• 当pq不为空时，执行

• 如果0 <= nr <R和0 <= nc <C，则

• dist [nr，nc，h2]：= d2

• 将[d2，nr，nc，h2]插入pq

• 如果d2 <dist [nr，nc，h2]，则

• 返回d

• 进行下一次迭代

• 从pq中删除一个元素并将其存储到d，r，c，h

• 如果dist [r，c，h] <d，则

• 如果r和c均为0，则

• 对于[[r + 1，c]，[r，c + 1]，[r-1，c]，[r，c-1]]中的每对(nr,nc)

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

示例

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))

输入值

[[2, 4, 5],[8, 6, 1]]

输出结果

4