假设我们有一个矩阵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不为空时,执行
如果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