Shortest Path in a Grid with Obstacles Elimination

Shortest Path in a Grid with Obstacles Elimination is a BFS problem with a twist: you can knock down up to k walls. The trick is realizing that the state is no longer just where you are — it is where you are plus how many eliminations you have left.

The slow way first

You might try a plain BFS or DFS that only tracks (row, col). But that is wrong: a cell can be reached in two very different situations — once with lots of eliminations left, once with none — and those are not the same. A naive visited set keyed only on position will block a better path. Re-exploring without any visited set, on the other hand, blows up into exponential time.

The question to ask: what fully describes my situation so I never need to redo work?

The idea: put k in the state

Make the BFS state a triple (row, col, k_left). Two visits to the same cell with the same remaining budget are truly identical, so we mark (row, col, k_left) as seen and never repeat it. Stepping onto a wall subtracts one from k_left; stepping onto an open cell leaves it unchanged. Because BFS expands in layers, the first time we pop the goal cell, its distance is the shortest.

The key insight: the budget k is part of your identity in the search, not a side counter.

Walk through it

Step through the animation. BFS starts at (0,0) with k = 1. The frontier expands outward; when it steps onto a #, that branch loses an elimination. The path that walks around the walls — (0,0) to (1,0) to (1,1) to (2,1) to (2,2) — reaches the goal in 4 steps without ever spending the budget.

Pseudocode

queue holds states (row, col, k_left, distance), start = (0, 0, k, 0)
seen = { (0, 0, k) }
while queue not empty:
    pop (r, c, k_left, dist)
    if (r, c) is the bottom-right corner:
        return dist
    for each neighbor (nr, nc) in bounds:
        nk = k_left - grid[nr][nc]        # wall costs one elimination
        if nk >= 0 and (nr, nc, nk) not seen:
            mark seen, push (nr, nc, nk, dist + 1)
return -1                                  # goal unreachable

The Python solution

def shortest_path(grid, k):
    R, C = len(grid), len(grid[0])
    q = deque([(0, 0, k, 0)])           # row, col, k_left, dist
    seen = {(0, 0, k)}
    while q:
        r, c, kl, d = q.popleft()
        if (r, c) == (R - 1, C - 1):
            return d
        for nr, nc in neighbors(r, c):
            nk = kl - grid[nr][nc]      # wall costs one
            if nk >= 0 and (nr, nc, nk) not in seen:
                seen.add((nr, nc, nk)); q.append((nr, nc, nk, d + 1))
    return -1

• The queue holds full states: (row, col, k_left, dist). BFS pops in increasing distance order.
• seen is keyed on (row, col, k_left) — the same cell with a different budget is a different state.
• if (r, c) == (R - 1, C - 1) returns the moment the goal is popped; BFS guarantees it is the shortest.
• nk = kl - grid[nr][nc] is the heart: an open cell is 0 (budget unchanged), a wall is 1 (budget drops).
• We only push when nk >= 0 — you cannot go below zero eliminations — and when the state is new.

Complexity

Every state (row, col, k_left) is enqueued at most once, so the whole search is bounded by the number of states, m * n * k. That is the payoff of folding k into the state — no cell-budget pair is ever redone.

When this pattern shows up

Practice