程序查找要增加高度以到达Python中的目标的最小高度
假设我们有一个矩阵M，其中M[r][c]代表那个单元的高度。如果我们当前位于左上角，并且想要转到右下角。仅当相邻单元格的高度小于或等于当前单元格的高度时，我们才能移动到相邻单元格（上，下，左，右）。在移动之前，我们可以增加任意数量的单元格的高度，因此我们必须找到需要增加的最小总高度，以便可以转到右下角的单元格。
所以，如果输入像
251然后输出将为4，因为我们可以采用以下路径[2，4，5，1]并将高度更改为此配置-
5为了解决这个问题，我们将遵循以下步骤-
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