BFS for Minimum Steps: Grids and State Spaces

Breadth-first search explores states in order of distance from the start: first everything one move away, then everything two moves away, and so on. In any graph where every move costs the same, the first time BFS reaches a state is along a shortest path. That makes it the default answer to "minimum number of moves / steps / transformations", whether the graph is an explicit grid or an implicit space of puzzle states generated on the fly.

Intuition

• A queue holds the frontier. Because states enter the queue in order of distance, they also leave in that order, so distances are discovered layer by layer.
• Mark a state as visited when you enqueue it, not when you dequeue it. Otherwise the same state can be enqueued many times from different neighbors, and the queue can blow up.
• The graph does not need to exist in memory. A state can be a grid cell, a lock combination string, a board configuration, or a tuple like (row, col, keys_collected). You only need a function that lists the neighbors of a state.
• Multi-source BFS: if the question is "distance to the nearest source", put all sources in the queue at distance 0 before starting. It is equivalent to adding a virtual super-source connected to all of them.
• 0-1 BFS: if some moves are free (cost 0) and others cost 1, use a deque: push 0-cost neighbors to the front and 1-cost neighbors to the back. The deque stays sorted by distance, like Dijkstra's algorithm without the heap.
• Compared with DFS, BFS finds shortest paths but stores a whole layer at once, so it needs more memory.

When to use it in interviews / OAs

• "Minimum moves / steps / minutes / transformations" with uniform move cost: mazes, knight moves, an elevator that jumps fixed distances, word ladder, open the lock, sliding puzzles.
• "Distance from every cell to the nearest X" or "how long until everything is infected / burned / rotten": multi-source BFS.
• Shortest path where the position alone is not enough state: you may break k walls, you hold a set of keys, you have a remaining fuel or a direction. Add that information to the state.
• Edge weights that are only 0 or 1: 0-1 BFS in O(V + E) instead of Dijkstra's O(E log V).
• Level-by-level processing: tree level order, "minimum depth", spreading processes that advance one layer per tick.

Template

Grid shortest path

from collections import deque

DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))


def shortest_path(grid: list[str], start: tuple[int, int], goal: tuple[int, int]) -> int:
    """Fewest moves from start to goal through '.' cells, or -1 if unreachable."""
    rows, cols = len(grid), len(grid[0])
    dist = {start: 0}  # doubles as the visited set
    q = deque([start])
    while q:
        r, c = q.popleft()
        if (r, c) == goal:
            return dist[(r, c)]
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "." and (nr, nc) not in dist:
                dist[(nr, nc)] = dist[(r, c)] + 1  # mark on enqueue
                q.append((nr, nc))
    return -1

To return the path itself, store parent[(nr, nc)] = (r, c) when enqueuing and walk back from the goal.

Implicit state graph

A lock has four wheels with digits 0 to 9; each move turns one wheel by one step. Some combinations are forbidden. States are strings, and their neighbors are generated on demand:

def open_lock(deadends: list[str], target: str) -> int:
    dead = set(deadends)
    if "0000" in dead:
        return -1
    dist = {"0000": 0}
    q = deque(["0000"])
    while q:
        s = q.popleft()
        if s == target:
            return dist[s]
        for i in range(4):
            digit = int(s[i])
            for nd in ((digit + 1) % 10, (digit - 1) % 10):
                t = s[:i] + str(nd) + s[i + 1:]
                if t not in dist and t not in dead:
                    dist[t] = dist[s] + 1
                    q.append(t)
    return -1

Multi-source BFS, one layer per tick

Rotten oranges (2) spoil fresh neighbors (1) every minute. Start from all rotten oranges at once and count layers:

def minutes_to_rot(grid: list[list[int]]) -> int:
    """Minutes until no fresh orange is left, or -1 if some never rot."""
    grid = [row[:] for row in grid]
    rows, cols = len(grid), len(grid[0])
    q = deque((r, c) for r in range(rows) for c in range(cols) if grid[r][c] == 2)
    fresh = sum(row.count(1) for row in grid)
    minutes = 0
    while q and fresh:
        for _ in range(len(q)):  # exactly the current layer
            r, c = q.popleft()
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2  # the grid itself marks visited
                    fresh -= 1
                    q.append((nr, nc))
        minutes += 1
    return -1 if fresh else minutes

BFS over an augmented state

You may walk through at most k walls. Reaching the same cell with more eliminations left is a different (and better) state, so the remaining budget is part of the state:

def shortest_with_eliminations(grid: list[list[int]], k: int) -> int:
    """Fewest moves from the top-left to the bottom-right cell, passing through at most k walls (1s)."""
    rows, cols = len(grid), len(grid[0])
    seen = {(0, 0, k)}
    q = deque([(0, 0, k, 0)])  # row, col, eliminations left, steps
    while q:
        r, c, left, steps = q.popleft()
        if (r, c) == (rows - 1, cols - 1):
            return steps
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                nl = left - grid[nr][nc]
                if nl >= 0 and (nr, nc, nl) not in seen:
                    seen.add((nr, nc, nl))
                    q.append((nr, nc, nl, steps + 1))
    return -1

0-1 BFS

Entering a wall costs 1 (you remove it), entering an empty cell costs 0. Find the minimum total cost:

def min_walls_to_remove(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    dist = [[float("inf")] * cols for _ in range(rows)]
    dist[0][0] = 0
    dq = deque([(0, 0)])
    while dq:
        r, c = dq.popleft()
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                nd = dist[r][c] + grid[nr][nc]
                if nd < dist[nr][nc]:
                    dist[nr][nc] = nd
                    if grid[nr][nc] == 0:
                        dq.appendleft((nr, nc))  # cost 0: same distance, go to the front
                    else:
                        dq.append((nr, nc))      # cost 1: next distance, go to the back
    return dist[rows - 1][cols - 1]

Unlike plain BFS, a cell can be improved after it was first reached, so 0-1 BFS relaxes distances the way Dijkstra does.

Complexity

• Time O(V + E): every state is enqueued once and every transition examined once. For a grid that is O(rows * cols); for the lock, 10^4 states with 8 neighbors each.
• Space O(V) for the visited set and the queue.
• Augmented states multiply V: the elimination problem has rows * cols * (k + 1) states.
• 0-1 BFS: O(V + E), each state may be pushed a constant number of extra times.

Common pitfalls

• Marking visited on dequeue instead of on enqueue: duplicates flood the queue and the run time explodes.
• list.pop(0) is O(n). Use collections.deque.
• Missing state. If two arrivals at the same cell can lead to different futures (different keys, budget, direction), the visited key must include that information.
• Using BFS with general weights. BFS is only correct when every move costs the same; for 0/1 costs use 0-1 BFS, otherwise Dijkstra.
• Off-by-one in layer counting. Count a layer only after it has been fully processed, and handle "already done at time 0" (no fresh oranges, start equals target).
• Unreachable targets. Return -1 (or whatever is asked) after the queue empties.
• Huge state spaces (for example 9! sliding-puzzle boards): encode states compactly (strings or tuples), and consider bidirectional BFS or A* when one-sided BFS is too slow.

Interview variations

• Shortest path in a binary matrix (8 directions), knight minimum moves, jump game variants on indices.
• Word ladder: neighbors by changing one letter; precompute wildcard buckets such as h*t for speed.
• Open the lock, sliding puzzle (the state is the board as a string), minimum genetic mutation.
• Rotting oranges, walls and gates, distance to the nearest 0, as far from land as possible: multi-source BFS.
• Shortest path with obstacle elimination, shortest path to collect all keys (state includes a key bit mask).
• Minimum cost to make the grid have a valid path, minimum obstacle removal: 0-1 BFS.
• Bus routes: BFS over routes (or stops) rather than individual stops to keep the graph small.