1
# Runtime: 1804 ms (Top 36.30%) | Memory: 15.4 MB (Top 76.73%)
2
class Solution:
3
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
4
        di = (0, 1, 0, -1)
5
        dj = (1, 0, -1, 0)
6
        m, n = len(heights), len(heights[0])
7
        visited = [[False] * n for _ in range(m)]
8
        h = [(0, 0, 0)]
9
        while h:
10
            effort, i, j = heappop(h)
11
            if visited[i][j]:
12
                continue
13
            visited[i][j] = True
14
            if i + 1 == m and j + 1 == n:
15
                return effort  ## have reached the (m-1, n-1) cell
16
            for k in range(4):
17
                ii, jj = i + di[k], j + dj[k]
18
                if 0 <= ii < m and 0 <= jj < n and not visited[ii][jj]:
19
                    neffort = max(effort, abs(heights[i][j] - heights[ii][jj]))
20
                    heappush(h, (neffort, ii, jj))
21
        return  ## cell (m-1, n-1) not reachable, should never happen