1293. Shortest Path in a Grid with Obstacles Elimination - Detailed Explanation

Problem Statement

You’re given an m×n binary grid grid where 0 represents an empty cell and 1 represents an obstacle. You start at the upper‑left corner (0,0) and must reach the lower‑right corner (m−1,n−1). You can move up, down, left, or right one cell at a time. You are also given an integer k—the maximum number of obstacles you can eliminate (i.e. treat as empty) along your path. Return the minimum number of steps to reach the destination, or −1 if it’s not possible within k eliminations.

Examples

Example 1

Input:  grid = 
 [[0,0,0],
  [1,1,0],
  [0,0,0],
  [0,1,1],
  [0,0,0]],
 k = 1
Output: 6
Explanation:  
The shortest path without elimination is length 10.  
By eliminating the obstacle at (1,0) or (1,1), you can cut it to 6 steps:
 (0,0)→(0,1)→(0,2)→(1,2)→(2,2)→(3,2)→(4,2).

Example 2

Input:  grid = 
 [[0,1,1],
  [1,1,1],
  [1,0,0]],
 k = 1
Output: -1
Explanation:
Even eliminating one obstacle, you cannot reach (2,2).

Constraints

• m == grid.length
• n == grid[i].length
• 1 ≤ m, n ≤ 40
• grid[i][j] is 0 or 1.
• 0 ≤ k ≤ m·n

Hints

1. A simple BFS tracks only (i,j), but here you must also track how many obstacles you’ve eliminated so far.
2. Use a 3D visited structure or a 2D array that stores, for each cell, the fewest eliminations used to get there.
3. Stop exploring a state if you’ve already arrived at the same cell with ≤ the same eliminations used.
4. Since m,n ≤ 40, the total states (i,j,elim) is at most 40·40·(k+1), which can be up to ~64K if k is large—but BFS will prune aggressively.

Approach: BFS Over (row, col, usedElim)

1. State = (r, c, e) where (r,c) is current position and e is how many obstacles eliminated so far.
2. Queue = double‑ended queue storing states, and we track distance (steps) by level‑order traversal.
3. Visited = 2D array bestElim[r][c] = minimum e seen so far at (r,c). Initialize all to +∞ except bestElim[0][0] = 0.
4. BFS Loop:
   • For each state in current level, try all four directions (nr,nc).
   • Let ne = e + grid[nr][nc] (increment if obstacle).
   • If ne > k or ne ≥ bestElim[nr][nc], skip.
   • Otherwise update bestElim[nr][nc] = ne and enqueue (nr,nc,ne).
   • If (nr,nc) is the target, immediately return steps+1.
5. If BFS exhausts without reaching target, return -1.

Step‑by‑Step Example (Example 1)

grid = [[0,0,0],
         [1,1,0],
         [0,0,0],
         [0,1,1],
         [0,0,0]], k=1

bestElim init: bestElim[0][0]=0, others=∞
queue = [(0,0,0)], steps=0

Level 0:
 (0,0,0) → neighbors:
  (1,0): ne = 0+1=1 ≤k and 1<∞ → bestElim[1][0]=1 enqueue (1,0,1)
  (0,1): ne = 0+0=0 <∞ → bestElim[0][1]=0 enqueue (0,1,0)

Level 1 (steps=1):
 process (1,0,1):
  → (2,0): ne=1+0=1 <∞ → bestElim[2][0]=1 enqueue
  → (1,1): ne=1+1=2>k skip
  → (0,0): ne=1+0=1 ≥ bestElim[0][0]=0 skip
 process (0,1,0):
  → (1,1): ne=0+1=1<∞ → bestElim[1][1]=1 enqueue
  → (0,2): ne=0+0=0<∞ → bestElim[0][2]=0 enqueue
  → ...

Continue BFS; upon first reach of (4,2) we’ll be at steps=6 → return 6.

Complexity Analysis

• Time: In the worst case we explore each cell with each possible e from 0…k. That’s O(m·n·k), but pruning when a better e already exists often cuts this dramatically.
• Space: O(m·n) for bestElim plus O(m·n·k) queue states in worst case.

Python Code