Problem statement

https://binarysearch.com/problems/Shortest-Path-by-Removing-K-Walls/

Solution

Equal to Leetcode 1293. Shortest Path in a Grid with Obstacles Elimination.

Complexity

It is O(m*n*k) for time and space.

Code

class Solution:
    def solve(self, grid, k):
        m, n = len(grid), len(grid[0])
        Q, v = deque([(0, 0, 0, k)]), set()
        
        while Q:
            steps, x, y, k = Q.popleft()
            if (x, y) == (n-1, m-1): return steps
            
            for dx, dy in (x, y-1), (x, y+1), (x-1, y), (x+1, y):
                if 0 <= dx < n and 0 <= dy < m and k - grid[dy][dx] >= 0:
                    new = (dx, dy, k - grid[dy][dx])
                    if new not in v:
                        v.add(new)
                        Q.append((steps + 1,) + new)
            
        return -1