Minimum Obstacle Removal to Reach Corner LeetCode solution in Python

1
class Solution:
2
    def minimumObstacles(self, grid: List[List[int]]) -> int:
3
        m, n = len(grid), len(grid[0])
4
        q = [(0, 0, 0)]
5
        dist = [[float("inf") for _ in range(n)] for _ in range(m)]
6

7
        while q:
8
            size = len(q)
9
            for _ in range(size):
10
                obs, x, y = heapq.heappop(q)
11
                if dist[x][y] < float("inf"):
12
                    continue
13
                obs += grid[x][y]
14
                dist[x][y] = obs
15
                if x + 1 < m:
16
                    heapq.heappush(q, (obs, x + 1, y))
17
                if x > 0:
18
                    heapq.heappush(q, (obs, x - 1, y))
19
                if y + 1 < n:
20
                    heapq.heappush(q, (obs, x, y + 1))
21
                if y > 0:
22
                    heapq.heappush(q, (obs, x, y - 1))
23
        return dist[m - 1][n - 1]