[LeetCode] 1631. Path With Minimum Effort

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

This problem cannot be solved by DP. Because for each cell, it can be reached from 4 directions.  There is no way to solve it base on optimal solution.

We may consider the absolute difference from cell A to cell B as the effort to travel from A to B. So the problem can be reduced to using Dijkstra algorithm to find the shortest path from (0,0) cell to (row-1, column-1) cell.

Time Complexity = O(M * N * Log ( M * N ))

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        ROW = len(heights)
        COLUMN = len(heights[0])
            
        heap = [(0,0,0)]
        visited = [[False] * COLUMN for _ in range(ROW)]
                
        while heap:
            for _ in range(len(heap)):
                e, y, x = heapq.heappop(heap)
                if visited[y][x]:
                    continue
                
                visited[y][x] = True

                if y == ROW - 1 and x == COLUMN - 1:
                    return e

                for dy, dx in [(-1,0), (1,0), (0,-1), (0,1)]:
                    ny, nx = y + dy, x + dx

                    if 0 <= ny < ROW and 0 <= nx < COLUMN and not visited[ny][nx]:               
                        ne = max(e, abs(heights[y][x] - heights[ny][nx]))
                        heapq.heappush(heap, (ne, ny, nx))
                    
        return -1