轻松掌握：1631号难题 - 最低成本路径刷题笔记

参考了这个题解
这句是一种剪枝策略，如果一个山峰有两条路径到达，会跳过高的那条记录

if d > dist[r][c]: continue

出现下面的问题是定义二维列表的的时候忘记加括号

TypeError: ‘float’ object is not subscriptable
if d>disMatrix[x][y]:
Line 10 in minimumEffortPath (Solution.py)
ret = Solution().minimumEffortPath(param_1)
Line 46 in _driver (Solution.py)
_driver()
Line 57 in (Solution.py)

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        direct = [0,1,0,-1,0]
        minHeap = [(0,0,0)]
        m,n = len(heights)-1,len(heights[0])-1
        disMatrix = [[float('inf')]*(n+1) for _ in range(m+1)]
        while minHeap:
            d,x,y = heappop(minHeap)
            if d>disMatrix[x][y]:
                continue
            
            if x == m and y == n:
                return d
            for i in range(4):
                nx,ny = x+direct[i],y+direct[i+1]
                if 0<=nx<=m and 0<=ny<=n:


                    nd = max(d,abs(heights[nx][ny]-heights[x][y]))
                    if nd<disMatrix[nx][ny]:
                        disMatrix[nx][ny] = nd
                        heappush(minHeap,(nd,nx,ny))
                
        

        

运行结果：