Shortest Path in a Grid with Obstacles Elimination
Last Updated: March 28, 2026
Understanding the Problem
At first glance, this looks like a standard shortest-path-in-a-grid problem. But there is a twist: we are allowed to eliminate up to k obstacles along the way. That changes things significantly, because now the "best" way to reach a cell depends not just on the position, but also on how many eliminations we have left.
Consider a simple example. If you reach cell (2, 3) with 3 eliminations remaining, that is a fundamentally different state than reaching the same cell with 1 elimination remaining. The first state has more options for the future, even though both arrived at the same location. This means a simple visited[row][col] array is not enough. We need to track the state as a triple: (row, col, remaining eliminations).
The key insight is that this is still a shortest path problem in an unweighted graph, just one 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 still guarantees the shortest path. The first time we reach the destination in any state, that is the optimal answer.
Key Constraints:
1 <= m, n <= 40-> The grid is small, at most 40 x 40 = 1,600 cells. But the state space includes 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), which is at most 40 x 40 x 1601 = about 2.56 million states.grid[0][0] == 0andgrid[m-1][n-1] == 0-> Start and end cells are always empty. No need for special handling.
Approach 1: BFS with State Tracking
Intuition
Standard grid BFS uses a 2D visited array because the state is just (row, col). But here, arriving at the same cell with different remaining eliminations leads to different futures. A cell you cannot pass through with 0 eliminations left becomes passable with 1 elimination left. So the state must include the number of remaining eliminations.
Think of it this way: imagine stacking k+1 copies of the grid on top of each other, one for each possible 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 one layer down (you spent an elimination). BFS on this 3D structure finds the shortest path that accounts for both distance and resource usage.
We track visited states with a 3D boolean array: visited[row][col][remainingK]. When we reach (m-1, n-1) at any layer, we return the current step count.
One important optimization: if k >= m + n - 3, we can guarantee a path of length m + n - 2 (the Manhattan distance). The shortest possible path from (0,0) to (m-1, n-1) requires exactly m - 1 downward moves and n - 1 rightward moves. That path passes through at most m + n - 3 interior cells (excluding start and end, which are guaranteed to be 0). If k is at least that large, we can blast through any obstacles on this direct path.
BFS guarantees shortest path because it explores all states at distance d before any state at distance d+1. The 3D state space (row, col, remainingK) captures all the information needed to make optimal decisions. Two states at the same cell but with different remaining eliminations are independent, because the one with more eliminations has strictly more future options.
The neat trick of computing newK = remK - grid[newRow][newCol] handles both cases cleanly. If the neighbor is empty (value 0), newK equals remK (no elimination used). If it is an obstacle (value 1), newK equals remK - 1 (one elimination used). We only proceed if 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.
BFS explores all reachable states equally, including those heading away from the destination. What if we prioritized states that are closer to the goal?
Approach 2: A* Search with State Tracking
Intuition
Standard BFS explores states in a blind, wave-like pattern. It does not know where the destination is, so it wastes time on states heading in the wrong direction. A* search fixes this by using a heuristic to estimate how far each state is from the goal, then prioritizing states with the smallest estimated total cost.
For this problem, the heuristic is the Manhattan distance from the current cell to the destination: (m - 1 - row) + (n - 1 - col). This is admissible because even with unlimited eliminations, you need at least that many steps to reach the bottom-right corner. Since the heuristic never overestimates, A* is guaranteed to find the optimal solution.
The priority of each state becomes steps + manhattan_distance(current, destination). States that have made good progress toward the goal get dequeued first, which can dramatically reduce the number of states explored compared to plain BFS.
A works because the Manhattan distance heuristic is admissible for 4-directional grid movement. The minimum number of steps from any cell (r, c) to (m-1, n-1) is at least (m-1-r) + (n-1-c), regardless of obstacles. Obstacles can only make the actual distance longer, never shorter. So the heuristic never overestimates, which guarantees A finds the optimal solution.
The practical benefit is that A focuses its search toward the destination. In the example walkthrough, every state along the optimal path has the same f-value (6), so A explores them in sequence without wasting time on states that move away from the goal.
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.