Leetcode: 1293. Shortest Path in a Grid with Obstacles Elimination

Problem Statement

Can we formulate the problem using graphs? Yes. The problem becomes do a Breadth-first search starting from node \((0, 0)\) and ending on \((n-1, m-1)\). Time and space complexity is \(O(N \times M \times K)\). 

from typing import List


class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        N = len(grid)
        M = len(grid[0])

        queue = []
        vis = [[[False] * (k + 1) for _ in range(M)] for _ in range(N)]

        queue.append((0, 1 if grid[0][0] == 1 else 0, 0, 0))
        for d, c, i, j in queue:
            if c > k:
                continue
            if vis[i][j][c]:
                continue
            vis[i][j][c] = True

            if i == N - 1 and j == M - 1:
                return d

            for di, dj in [[+0, +1], [+0, -1], [+1, +0], [-1, +0]]:
                nd = d + 1
                nc = c + (1 if grid[i][j] == 1 else 0)
                if 0 <= di + i < N and 0 <= dj + j < M and nc <= k:
                    queue.append((nd, nc, di + i, dj + j))

        return -1


assert (
    Solution().shortestPath([[0, 0, 0], [1, 1, 0], [0, 0, 0], [0, 1, 1], [0, 0, 0]], 1)
    == 6
)
assert Solution().shortestPath([[0, 1, 1], [1, 1, 1], [1, 0, 0]], 1) == -1