1293. Shortest Path in a Grid with Obstacles Elimination

link

Mark the special status to the seen set (n times elimination)

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:

        m = len(grid)
        n = len(grid[0])


        dq = deque([((0, 0), 0, 0)])

        s = set()

        while dq:

            lens = len(dq)
            for _ in range(lens):
                (i, j), e, step = dq.popleft()

                if (i, j, e) in s:
                    continue

                s.add((i, j, e))

                if grid[i][j] == 1:
                    e += 1
                
                if e > k:
                    continue

                if (i, j) == (m-1, n-1):
                    return step

                for x, y in [(0,1),(0,-1),(1,0),(-1,0)]:
                    if not (0 <= i + x < m and 0 <= j + y < n):
                        continue
                    dq.append(((i+x, j+y), e, step+1))
                    
        return -1