LC 1293 [H] Shortest Path in a Grid with Obstacles Elimination - ALawliet/algorithms GitHub Wiki

DIRS = [(1,0),(-1,0),(0,1),(0,-1)]

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        n_rows = len(grid)
        n_cols = len(grid[0])
        
        # 1x1 edge case
        if n_rows == 1 and n_cols == 1:
            return 0
        
        Q = deque([ (0, 0, 0, 0) ]) # r, c, obstacle count, path len
        visited = set()
         
        while Q:
            r, c, obstacles_smashed, path_len = Q.popleft()
            
            if (r, c) == (n_rows - 1, n_cols - 1):
                return path_len
            
            for dr, dc in DIRS:
                nr = r + dr
                nc = c + dc

                if 0 <= nr < n_rows and 0 <= nc < n_cols:
                    # we can potentially queue 2 states per direction
                    
                    # there is an obstacle and we have enough to smash it
                    if grid[nr][nc] == 1 and obstacles_smashed < k and (nr, nc, obstacles_smashed + 1) not in visited:
                        Q.append( (nr, nc, obstacles_smashed + 1, path_len + 1) )
                        visited.add( (nr, nc, obstacles_smashed + 1) )
                        
                    # there is no obstacle and we just take the open space
                    if grid[nr][nc] == 0 and (nr, nc, obstacles_smashed) not in visited:    
                        Q.append( (nr, nc, obstacles_smashed, path_len + 1) )
                        visited.add( (nr, nc, obstacles_smashed) )
                        
        return -1