1631. Path With Minimum Effort - cocoder39/coco39_LC GitHub Wiki

1631. Path With Minimum Effort

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        DIR = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        m, n = len(heights), len(heights[0])
        dist = [[float("inf")] * n for i in range(m)]
        dist[0][0] = 0
        min_heap = [(0, 0, 0)] # effort, row, col
        while min_heap:
            e, r, c = heapq.heappop(min_heap)
            if r == m-1 and c == n-1:
                return e
            
            for x, y in DIR:
                if 0 <= r+x < m and 0 <= c+y < n:
                    effort = max(e, abs(heights[r+x][c+y] - heights[r][c]))
                    if effort < dist[r+x][c+y]:
                        dist[r+x][c+y] = effort
                        heapq.heappush(min_heap, (effort, r+x, c+y))
                    
        return -1