Problem statement

https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/

Solution

just use bfs with state (x, y, k), where (x, y) are coordinates and k is number of obstacles we still can remove. As visited states we keep just coordinates, without k.

Complexity

Complexity is O(m*n*k). It can be pruned a bit if we do some early breaks, in fact if k is big enough, > m + n - 2, then we can always choose the shortest path with m+n-2 steps. So, complexity will be O(m*n*(m+n)). adding line if k >= m + n - 2: return m + n - 2 in the beginning go from 800ms to 72ms.

Code

class Solution:
    def shortestPath(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