Shortest Path in a Grid with Obstacles Elimination

To find the shortest path from the upper left corner to the lower right corner, given that you can eliminate at most k obstacles, you can use a Breadth-First Search (BFS) with a small modification to handle the obstacles.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from collections import deque

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        visited = set([(0, 0, k)])
        queue = deque([(0, 0, k, 0)]) # row, col, remaining k, steps

        while queue:
            row, col, remain_k, steps = queue.popleft()

            # If reached the destination, return steps
            if row == m - 1 and col == n - 1:
                return steps

            for dr, dc in directions:
                nrow, ncol = row + dr, col + dc
                if 0 <= nrow < m and 0 <= ncol < n and (nrow, ncol, remain_k - grid[nrow][ncol]) not in visited:
                    if grid[nrow][ncol] == 1 and remain_k > 0: # If there's an obstacle and we can eliminate
                        queue.append((nrow, ncol, remain_k - 1, steps + 1))
                        visited.add((nrow, ncol, remain_k - 1))
                    elif grid[nrow][ncol] == 0: # If no obstacle
                        queue.append((nrow, ncol, remain_k, steps + 1))
                        visited.add((nrow, ncol, remain_k))

        return -1

This code defines a BFS that visits every cell with a different remaining k separately. If it encounters an obstacle, it reduces k by 1, but only if there is at least one k left. If it reaches the destination, it returns the number of steps taken. If the queue becomes empty without reaching the destination, it returns -1.

The time complexity of this solution is O(m * n * k), where m is the number of rows, n is the number of columns, and k is the number of allowed obstacle eliminations. The space complexity is also O(m * n * k) due to the visited set and the queue.