class Solution:

def minimumEffortPath(self, heights: List[List[int]]) -> int:

    row = len(heights)

    col = len(heights[0])

    difference_matrix = [[math.inf]*col for _ in range(row)]

    difference_matrix[0][0] = 0

    visited = [[False]*col for _ in range(row)]

    queue = [(0, 0, 0)]  # difference, x, y

    while queue:

        difference, x, y = heapq.heappop(queue)

        visited[x][y] = True

        for dx, dy in [[0, 1], [1, 0], [0, -1], [-1, 0]]:

            adjacent_x = x + dx

            adjacent_y = y + dy

            if 0 <= adjacent_x < row and 0 <= adjacent_y < col and not visited[

                    adjacent_x][adjacent_y]:

                current_difference = abs(

                    heights[adjacent_x][adjacent_y]-heights[x][y])

                max_difference = max(

                    current_difference, difference_matrix[x][y])

                if difference_matrix[adjacent_x][adjacent_y] > max_difference:

                    difference_matrix[adjacent_x][adjacent_y] = max_difference

                    heapq.heappush(

                        queue, (max_difference, adjacent_x, adjacent_y))

    return difference_matrix[-1][-1]