Learning On the Way

1293. Shortest Path in a Grid with Obstacles Elimination

You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step. Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.

BFS

This question is very similar to 787. Cheapest Flights Within K Stops

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        from collections import deque
        
        # irow, icol, steps, number of obstacle removal
        dq = deque([(0, 0, 0, 0)])
        
        m, n = len(grid), len(grid[0])
        
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        lowest = [[float('inf')] * n for _ in range(m)] # The minimum number of obstacles that need to be removed
        lowest[0][0] = 0
        
        def getNeighbors(r, c):
            for dx, dy in dirs:
                newr, newc = r + dx, c + dy
                if 0 <= newr < m and 0 <= newc < n:
                    yield newr, newc
        
        while dq:
            r, c, nstep, nremoval = dq.popleft()
            if r == m - 1 and c == n - 1:
                return nstep
            
            for newr, newc in getNeighbors(r, c):
                if grid[newr][newc] and nremoval == k:
                    continue
                nremoval_new = nremoval + grid[newr][newc]
                if lowest[newr][newc] > nremoval_new:
                    lowest[newr][newc] = nremoval_new
                    dq.append((newr, newc, nstep + 1, nremoval_new))
                
        return -1