1
class Solution:
2
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
3
        Q = [[0, 0, k]]  # m, n, remaining elimination quota
4
        rows, cols = len(grid), len(grid[0])
5
        V, counter = {
6
            (0, 0): k
7
        }, 0  # I use a V to keep track of how cells have been visited
8

9
        while Q:
10
            frontier = []
11
            for m, n, rem in Q:
12
                if m == rows - 1 and n == cols - 1:
13
                    return counter
14
                for dm, dn in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
15
                    if 0 <= m + dm < rows and 0 <= n + dn < cols:  # check inbound
16
                        if grid[m + dm][n + dn] == 0:
17
                            if (m + dm, n + dn) not in V or V[
18
                                (m + dm, n + dn)
19
                            ] < rem:  # if not visited or could be visited with fewer elimination
20
                                frontier.append([m + dm, n + dn, rem])
21
                                V[(m + dm, n + dn)] = rem
22
                        elif rem > 0:  # I see a wall and I can still eliminate
23
                            if (m + dm, n + dn) not in V or V[
24
                                (m + dm, n + dn)
25
                            ] < rem - 1:  # if not visited or could be visited with fewer elimination
26
                                frontier.append([m + dm, n + dn, rem - 1])
27
                                V[(m + dm, n + dn)] = rem - 1
28
            Q = frontier
29
            counter += 1
30

31
        return -1