Minimum Cost to Make at Least One Valid Path in a Grid LeetCode solution in Python

1
class Solution:
2
    def minCost(self, grid: List[List[int]]) -> int:
3
        changes = [
4
            [float("inf") for _ in range(len(grid[0]))] for _ in range(len(grid))
5
        ]
6
        heap = [(0, 0, 0)]
7
        dirn = [(0, 1), (0, -1), (1, 0), (-1, 0)]
8
        while heap:
9
            dist, r, c = heapq.heappop(heap)
10
            if (
11
                r >= len(grid)
12
                or r < 0
13
                or c >= len(grid[0])
14
                or c < 0
15
                or changes[r][c] <= dist
16
            ):
17
                continue
18
            if r == len(grid) - 1 and c == len(grid[0]) - 1:
19
                return dist
20
            changes[r][c] = dist
21
            for i in range(1, 5):
22
                if i == grid[r][c]:
23
                    heapq.heappush(heap, (dist, r + dirn[i - 1][0], c + dirn[i - 1][1]))
24
                else:
25
                    heapq.heappush(
26
                        heap, (dist + 1, r + dirn[i - 1][0], c + dirn[i - 1][1])
27
                    )
28
        return dist