Shortest Path in a Grid with Obstacles Elimination
Understanding the Problem
This is a shortest-path-in-a-grid problem with one extra rule: we are allowed to eliminate up to k obstacles along the way. That rule changes how we define progress, because the best way to reach a cell now depends on the position and on how many eliminations we have left.
Reaching cell (2, 3) with 3 eliminations remaining is a different situation from reaching the same cell with 1 elimination remaining. The first leaves more options for the rest of the walk, even though both arrived at the same location. A plain visited[row][col] array cannot tell those two situations apart. We need to track the state as a triple: (row, col, remaining eliminations).
With that triple as the state, this is still a shortest path problem in an unweighted graph, now with a larger state space. Each state is (row, col, k_remaining), and each move costs exactly 1 step. Since all edges have equal weight, BFS visits states in order of increasing distance, so the first time we reach the destination in any state is the optimal answer.
Key Constraints:
1 <= m, n <= 40-> The grid has at most 40 x 40 = 1,600 cells, but the state space also has the k dimension.1 <= k <= m * n-> k can be up to 1,600, so the total state space is m x n x (k+1), at most 40 x 40 x 1601 = about 2.56 million states. That is small enough for BFS to explore exhaustively.grid[0][0] == 0andgrid[m-1][n-1] == 0-> Start and end cells are always empty, so the corners need no special handling.
Approach 1: BFS with State Tracking
Intuition
Standard grid BFS uses a 2D visited array because the state is (row, col). Here, arriving at the same cell with different remaining eliminations leads to different sets of future moves. A cell that is blocked with 0 eliminations left is passable with 1 elimination left. The state must therefore include the number of remaining eliminations.
One way to visualize the state space is k+1 stacked copies of the grid, one per value of remaining eliminations (0, 1, 2, ..., k). Moving to an empty cell keeps you on the same layer. Moving to an obstacle cell drops you to the layer below (one elimination spent). BFS over this layered structure finds the shortest path while accounting for resource usage.
We track visited states with a 3D boolean array visited[row][col][remainingK]. The first time BFS dequeues a state at (m-1, n-1) on any layer, the current step count is the answer.
There is also a shortcut. If k >= m + n - 3, the answer is exactly m + n - 2 (the Manhattan distance). The shortest possible path from (0,0) to (m-1, n-1) makes m - 1 downward moves and n - 1 rightward moves, passing through at most m + n - 3 interior cells (start and end are guaranteed empty). When k is at least that large, every interior cell on that direct path can be eliminated if needed, so no obstacle can block it.
BFS reports the shortest path because it dequeues all states at distance d before any state at distance d+1, so the first dequeue of any destination state carries the minimum step count.
The move uses one expression for both cases: newK = remK - grid[newRow][newCol]. An empty neighbor (value 0) gives newK = remK (no elimination used); an obstacle neighbor (value 1) gives newK = remK - 1 (one elimination used). The move is allowed only when newK >= 0.
Algorithm
- If k >= m + n - 3, return m + n - 2 immediately (Manhattan distance shortcut).
- Create a queue and add the starting state (0, 0, k) with step count 0.
- Create a 3D visited array of size m x n x (k+1). Mark (0, 0, k) as visited.
- While the queue is not empty, dequeue a state (row, col, remainingK, steps).
- If (row, col) is the destination (m-1, n-1), return steps.
- For each of the 4 neighbors (newRow, newCol):
- If the neighbor is empty (grid value 0) and (newRow, newCol, remainingK) is not visited, add it to the queue with steps + 1.
- If the neighbor is an obstacle (grid value 1) and remainingK > 0 and (newRow, newCol, remainingK - 1) is not visited, add it to the queue with steps + 1.
- If the queue empties without reaching the destination, return -1.
Example Walkthrough
Code
- Time Complexity: O(m n k). Each state (row, col, remainingK) is visited at most once. There are m n (k+1) possible states. For each state, we check 4 neighbors, which is O(1) work.
- Space Complexity: O(m n k). The visited array has m n (k+1) entries. The BFS queue can hold at most that many states as well.
The next approach keeps the same state space but orders the search by an estimate of remaining distance, so it expands fewer states before reaching the goal.
Approach 2: A* Search with State Tracking
Intuition
BFS expands states purely in order of distance from the start, with no information about where the destination is, so it expands many states that lead away from the goal. A* search adds a heuristic that estimates how far each state is from the goal, then expands states with the smallest estimated total cost first.
The heuristic here is the Manhattan distance from the current cell to the destination: (m - 1 - row) + (n - 1 - col). It is admissible because reaching the bottom-right corner takes at least that many steps even with unlimited eliminations, so the estimate never exceeds the true remaining distance. An admissible heuristic guarantees A* returns the optimal path.
The priority of each state is steps + manhattan_distance(current, destination). States that have made progress toward the goal are dequeued first, which reduces the number of states expanded compared to plain BFS.
Algorithm
- If k >= m + n - 3, return m + n - 2 (same Manhattan shortcut).
- Create a min-heap ordered by f = steps + heuristic. Add (0, 0, k) with steps 0 and f = 0 + (m-1) + (n-1).
- Create a 3D visited array. Mark (0, 0, k) as visited.
- While the heap is not empty, extract the state with the smallest f-value.
- If it is the destination, return steps.
- For each of the 4 neighbors, compute newK and the new f-value. If the state is valid and unvisited, add it to the heap.
- If the heap empties, return -1.
Example Walkthrough
Code
- Time Complexity: O(m n k log(m n k)). In the worst case, A visits all m n (k+1) states. Each priority queue operation costs O(log(m n k)). In practice, A* visits far fewer states than BFS.
- Space Complexity: O(m n k). Same as BFS: the visited array and priority queue can each hold up to m n (k+1) entries.