1631.最小体力消耗路径

https://leetcode-cn.com/problems/path-with-minimum-effort/

Dijkstra 变种

一开始以为是dp，但问题是这种求相邻结点高度差最大值的状态不能累加，即没有递推方程。

最后还是用bfs+贪心

class Solution:
    def minimumEffortPath(self, heights) -> int:
        m = len(heights)
        n = len(heights[0])
        dirs = [0, 1, 0, -1, 0]
        # 返回(x, y)的邻节点
        def adj(x, y):
            neighbors = []
            for i in range(4):   #上下左右四个方向
                nx = x + dirs[i]
                ny = y + dirs[i+1]
                if nx < 0 or nx >= m or ny < 0 or ny >= n:
                    continue
                neighbors.append((nx, ny))

            return neighbors

        # effortTo[i][j] 表示 (0,0)-->(i,j)的最小消耗
        effortTo = [[sys.maxsize] * n for _ in range(m)]
        effortTo[0][0] = 0
        #最小堆，存储tuple（到某点体力值，某点坐标x、y）
        pq = []
        heapq.heappush(pq, (0,0,0))
        while pq:
            curEffortFromStart, curX, curY = heapq.heappop(pq)
            if curX == m-1 and curY == n-1:
                return curEffortFromStart
            if curEffortFromStart > effortTo[curX][curY]:
                continue
            for neigh in adj(curX, curY):
                nextX = neigh[0]
                nextY = neigh[1]
                #比较【高度差】 与 【记录表】，取较大值作为到下一个节点体力值
                effortToNext = max(
                    abs(heights[curX][curY] - heights[nextX][nextY]),
                    curEffortFromStart
                )
                #找到更小的，更新记录表并加入堆
                if effortToNext < effortTo[nextX][nextY]:                   
                    effortTo[nextX][nextY] = effortToNext
                    heapq.heappush(pq, (effortToNext, nextX, nextY))
        # 无法到达终点
        return -1