Shortest Path in a Grid with Obstacles Elimination: BFS with State

You are given an m x n grid of 0s and 1s, where 0 represents an empty cell and 1 represents an obstacle. You can move up, down, left, or right from any empty cell. You can also eliminate at most k obstacles along the way. Find the shortest path from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1). Return the length of the shortest path, or -1 if no such path exists.

This is LeetCode 1293: Shortest Path in a Grid with Obstacles Elimination, and it is one of the best problems for learning how to extend BFS with an extra state dimension. The core idea applies any time you have a limited resource that unlocks new paths.

Why this problem matters

Standard shortest-path-in-a-grid problems use BFS with a visited set of (row, col). This problem adds a twist: you have a budget of k obstacle eliminations. That means two visits to the same cell are not equivalent. Arriving at (2, 3) with 2 eliminations remaining is better than arriving with 0 remaining, because you have more flexibility for the rest of the path.

This "extra dimension" pattern shows up repeatedly. Any time you have a resource that gets consumed along the path (fuel, keys, lives, budget), you extend the BFS state to include that resource. The visited set becomes (row, col, resource_remaining) instead of just (row, col).

Once you internalize this pattern here, you can apply it to problems like "Shortest Path to Get All Keys" (LeetCode 864), "Minimum Moves to Reach Target with Rotations" (LeetCode 1210), and any BFS problem where a limited resource changes which moves are available.

The key insight

Think of the grid as having k + 1 layers stacked on top of each other. Layer i represents the grid when you have i eliminations remaining. Moving to an empty cell keeps you on the same layer. Moving to an obstacle cell drops you down one layer (you spend one elimination). The problem becomes: find the shortest path from (0, 0, k) to (m-1, n-1, any_layer) in this 3D graph.

BFS naturally handles this. Each state in the queue is (row, col, remaining_eliminations). When you dequeue a state and explore its neighbors:

1. If the neighbor is empty (grid[nr][nc] == 0), enqueue (nr, nc, remaining) on the same layer.
2. If the neighbor is an obstacle (grid[nr][nc] == 1) and remaining > 0, enqueue (nr, nc, remaining - 1) on the layer below.
3. If the neighbor is an obstacle and remaining == 0, skip it. You cannot afford to eliminate it.

The visited set tracks (row, col, remaining) triples. You mark a state as visited when you enqueue it, not when you dequeue it, to prevent duplicates in the queue.

Since BFS explores level by level, the first time you reach the destination (m-1, n-1) at any remaining value, that is the shortest path. You return immediately.

An important optimization

If k is large enough, specifically k >= m + n - 3, then you have enough eliminations to walk straight from (0, 0) to (m-1, n-1) along the shortest Manhattan path, eliminating every obstacle in the way. The shortest possible path length is m + n - 2, and you can return it immediately or cap k at m + n - 3 to reduce the state space. This optimization is critical for passing time limits on large inputs.

The solution

from collections import deque

def shortest_path(grid: list[list[int]], k: int) -> int:
    m, n = len(grid), len(grid[0])
    if m == 1 and n == 1:
        return 0

    k = min(k, m + n - 3)
    queue = deque([(0, 0, k, 0)])
    visited = {(0, 0, k)}

    while queue:
        r, c, remaining, steps = queue.popleft()
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n:
                nk = remaining - grid[nr][nc]
                if nk >= 0 and (nr, nc, nk) not in visited:
                    if nr == m - 1 and nc == n - 1:
                        return steps + 1
                    visited.add((nr, nc, nk))
                    queue.append((nr, nc, nk, steps + 1))

    return -1

Let's walk through what each piece does.

The function starts by handling the trivial case of a 1x1 grid (the start is the destination, return 0). Then it caps k at m + n - 3 since you never need more eliminations than the minimum path length minus one.

The BFS queue stores tuples of (row, col, remaining_eliminations, steps). The visited set stores (row, col, remaining) triples. We start at (0, 0) with k eliminations and 0 steps taken.

For each state we dequeue, we check all four neighbors. The key line is nk = remaining - grid[nr][nc]. If the neighbor is empty (grid[nr][nc] == 0), nk stays the same as remaining. If it is an obstacle (grid[nr][nc] == 1), nk drops by one. If nk is negative, we cannot afford the elimination and skip that neighbor.

We check for the destination before adding to the visited set and queue. This is an optimization: the moment we find a path to the bottom-right corner, we return immediately. Since BFS processes states in order of increasing steps, this is guaranteed to be the shortest path.

Visual walkthrough

Let's trace through the BFS on our example grid with k = 1. Watch how the algorithm explores states with their remaining elimination counts, and how eliminating an obstacle opens up a shorter path.

The BFS found the shortest path in 6 steps by eliminating the obstacle at (1, 0) and walking straight down the left column. Without the elimination, the path would have to wind around both sets of obstacles, taking 10 steps. The extra state dimension of remaining_eliminations is what lets BFS discover this shortcut.

Complexity analysis

Time is O(m * n * k) where m is rows, n is columns, and k is the maximum eliminations (after capping). Each cell can be visited with up to k + 1 different remaining values, and each visit does constant work (checking four neighbors). With the k = min(k, m + n - 3) optimization, this becomes O(m * n * (m + n)) in the worst case.

Space is O(m * n * k) for the visited set and the BFS queue. The visited set stores at most m * n * (k + 1) states. The queue holds at most one level of BFS states at a time, but the visited set dominates.

The building blocks

1. BFS with extra state dimensions

The pattern of extending BFS state beyond just position:

queue = deque([(start_row, start_col, initial_resource, 0)])
visited = {(start_row, start_col, initial_resource)}

while queue:
    r, c, resource, steps = queue.popleft()
    for nr, nc in neighbors(r, c):
        new_resource = update_resource(resource, grid[nr][nc])
        if valid(new_resource) and (nr, nc, new_resource) not in visited:
            visited.add((nr, nc, new_resource))
            queue.append((nr, nc, new_resource, steps + 1))

This is the general template. The "resource" could be obstacle eliminations, keys collected, fuel remaining, or any consumable. The visited set must include the resource state to avoid revisiting with the same or worse resource levels. You will reuse this pattern in "Shortest Path to Get All Keys," "Minimum Cost to Make at Least One Valid Path," and any BFS where different paths to the same cell are not equivalent.

2. Obstacle elimination as resource management

The insight of treating obstacles as a consumable budget:

nk = remaining - grid[nr][nc]
if nk >= 0:
    # can move here (either free cell or affordable elimination)

By subtracting the grid value directly, you handle both empty cells and obstacles in one line. Empty cells cost 0, obstacles cost 1. This is cleaner than branching with if grid[nr][nc] == 1. The same pattern works for any grid where cells have different traversal costs that consume a limited resource.

Edge cases

Before submitting, think through these scenarios:

• k >= m + n - 3: you have enough eliminations to walk the shortest Manhattan path. The answer is m + n - 2. The k cap handles this automatically.
• 1x1 grid: the start is the destination. Return 0 regardless of the grid value or k.
• No obstacles: standard BFS shortest path. The elimination budget is irrelevant, and the answer is m + n - 2.
• All obstacles with enough k: if the grid is full of 1s but k >= m + n - 3, you can still walk the shortest path by eliminating every obstacle along the way.
• Destination unreachable: if obstacles block all paths and k is too small, BFS exhausts all states and returns -1.
• k = 0: no eliminations allowed. This reduces to a standard shortest path in a grid, only traversing empty cells.

From understanding to recall

You have seen how BFS with an extra state dimension solves this problem: treat each (row, col, remaining) triple as a unique node, and let BFS find the shortest path through this 3D graph. The logic is clean and the code is compact. But reproducing it under interview pressure requires more than understanding.

The details that trip people up are small but costly. Do you subtract the grid value before or after the bounds check? Do you check for the destination before or after adding to visited? Do you cap k at m + n - 3 or m + n - 2? These are not conceptual gaps. They are recall gaps, and they cost people offers.

Spaced repetition is how you close them. You practice writing the extended BFS state, the resource update line, and the early termination check from memory at increasing intervals. After a few rounds, you see "limited resource BFS" in a problem description and the template flows out without hesitation.

Related posts

• Shortest Path in Binary Matrix - BFS shortest path on a grid without the extra state dimension, the simpler baseline version
• Rotting Oranges - Multi-source BFS on a grid, another essential BFS grid pattern
• Number of Islands - The foundational grid traversal problem that teaches DFS flood fill on a 2D grid

CodeBricks breaks this problem into its BFS-with-state and resource-management building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a BFS problem with an extra dimension shows up in your interview, you do not think about it. You just write it.