BFS over an augmented state

38 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A 3 by 3 grid where some cells are walls (#). You walk from the top left to the bottom right, one step at a time, and you are allowed to break through at most k = 1 wall. What is the fewest steps? Grid: row 0 is . . ., row 1 is # # ., row 2 is . # . with a wall at (1,0), (1,1), (2,1). By hand you try routes: around the right side, (0,0) → (0,1) → (0,2) → (1,2) → (2,2), four steps, no wall broken. Or straight down through (1,0): (0,0) → (1,0) break → (2,0) → then (2,1) is another wall, no break left. Dead end. So four.

Plain breadth-first search on cells fails here, and it is worth seeing why. BFS marks a cell visited the first time it is reached. Suppose you reach (1,2) first by breaking a wall, with zero breaks left. Later a route reaches (1,2) with one break still in hand, which is a better situation, but the cell is already marked, so that route is thrown away. The cell alone is not enough to describe where you are; what you still have matters.

Build the structure, one piece at a time

Piece one: the state. Instead of a cell, a node is a pair (cell, breaks left). Two visits to the same cell with different breaks left are different nodes. For keys-and-doors problems the extra part is the set of keys held; for a car that can only turn in some orientations it is the orientation; for a rotating domino it is horizontal or vertical.

Piece two: moves between states. From (cell, b), a step to an open neighbour gives (neighbour, b); a step onto a wall is allowed only if b > 0 and gives (neighbour, b − 1).

Piece three: ordinary BFS over these states, with a visited set keyed by the whole pair. The answer is the steps at the first state whose cell is the target, with any number of breaks left.

Why it is correct

BFS finds shortest paths in any graph whose edges all cost one step. The graph here has states as nodes, and each move is one step, so BFS over states gives the fewest steps to every state. The target is "any state at the goal cell", so the first such state popped is the answer. The visited set keyed by (cell, breaks) never discards a route that is in a different situation, which is what fixed the failure of cell-only BFS.

number of states = m × n × (k + 1)

A small pruning keeps it exact and faster: if k is at least the Manhattan distance, the straight route breaking every wall in the way is optimal, so return that distance at once.

Why it is fast

Each state is pushed and popped at most once, with four moves examined: O(m × n × k). The cost is multiplied by the size of the extra part of the state, so keep that part as small as the problem allows; a set of K keys is a K-bit mask, giving 2^K states per cell. Trying all routes by hand is exponential in the path length.

How to recognise it in an interview

A shortest-path question where the rules depend on something you carry or on how you arrived: "eliminate up to k obstacles", "collect all keys", "visit every node", "the car can be facing two ways", "a tile that rotates". Say: "The position alone does not determine the future, so my BFS node is (position, extra state) and visited is keyed by the whole pair." Shortest Path in a Grid with Obstacles Elimination is this exactly. Shortest Path to Get All Keys uses (cell, key bitmask). Shortest Path Visiting All Nodes uses (node, bitmask of visited nodes), with every node as a starting source.

02The idea in one line

The node is (position, extra state): keys held, obstacles left, parity.

Reach for it when: Shortest path with obstacle elimination, all keys, visiting all nodes, sliding puzzle.

Cost: O(states · edges) time.

03The walk-through, step by step

The video works one example: Obstacle elimination (k=1) on a 3×3 grid. These are its captions in order, so you can follow without the video or check a step you missed.

1. The visited set is keyed by (cell, k left), not the cell alone
2. Pop (0,0,1): stepping onto # spends k → (0,1,0)
3. Pop (0,1,0) at 1: push (0,2,0), (0,0,0)
4. Pop (1,0,1): stepping onto # spends k → (1,1,0)
5. Pop (0,2,0) at 2: push (1,2,0)
6. Pop (0,0,0) at 2: push (1,0,0)
7. Pop (1,1,0) at 2: push (2,1,0)
8. Pop (2,0,1) at 2: push (2,1,1)
9. Pop (1,2,0) at 3: push (2,2,0)
10. (2,2) reached in 4 steps by breaking through the wall
11. States = cells × (k+1): O(m·n·k)

04Asked at Google

7 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Graphs: Grid flood fill (components), Multi-source BFS, BFS shortest path (unweighted), 0-1 BFS (deque), DFS three-colour cycle detection, Topological sort (Kahn's), Union–Find (disjoint sets), Dijkstra (weighted shortest path), Bellman–Ford with k rounds, Minimum spanning tree, Bipartite colouring, Eulerian path (Hierholzer), Bridges / articulation (low-link), Clone / traverse with a visited map, Implicit graph (states as nodes).