BFS-Specific

What is this?

None of these three problems hands you a graph. A combination lock's states are the 10,000 four-digit codes; a board game's states are its squares, numbered along a path that reverses every row; and the last problem does not even ask a shortest-path question — it asks for the cell minimising the sum of distances to every building, which needs one BFS per building and an accumulator.

The traversal is the same queue you have written many times. Where the difficulty lives is the neighbour function.

💡 Fun fact: Shortest Distance from All Buildings is the one that is not a shortest-path problem at all. You want the empty cell minimising the total walk to every building, so you run a BFS from each building and add its distances into a running grid — plus a second grid counting how many buildings reached each cell. That reach count is what filters out cells which look excellent because a wall hides two of the buildings from them. Running the BFS from the buildings rather than from the candidate cells is what keeps it O(buildings × mn) instead of O(cells × mn).

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: define the state and its neighbours, and the BFS writes itself. The graph is never stored — it is generated one state at a time, which is the only reason a 10,000-node search costs nothing.

1. A state that is a string

q, seen = deque([("0000", 0)]), {"0000"}
while q:
    s, d = q.popleft()
    if s == target: return d
    for i in range(4):                                  # 4 dials
        for delta in (1, -1):                           # 2 directions
            t = s[:i] + str((int(s[i]) + delta) % 10) + s[i+1:]
            if t not in seen and t not in dead:
                seen.add(t); q.append((t, d + 1))

Eight neighbours per state, and % 10 is what makes 9 → 0 and 0 → 9 wrap without a branch. Deadends are simply states never enqueued — but check "0000" before the loop, because a deadend at the start makes the answer -1 and the loop as written would happily return 0 if the target were also "0000".

The whole space is 10,000 states, so the search is bounded no matter how the input looks.

2. A state that is a square, and a numbering that snakes

def cell(num):                                          # 1-indexed square → (row, col)
    r, c = divmod(num - 1, n)
    row = n - 1 - r                                     # numbering starts at the BOTTOM
    col = c if r % 2 == 0 else n - 1 - c                # every other row reverses
    return row, col

This conversion is the problem. From square num the moves are num+1 … num+6, and if the destination square holds a ladder or snake you go where it points instead — and you do not roll again. Marking dest as seen rather than nxt is what keeps that distinction straight; marking the wrong one produces answers that are almost right.

3. Many searches, one accumulator

total = [[0] * n for _ in range(m)]
reach = [[0] * n for _ in range(m)]
for each building:
    BFS from it, and for every empty cell it reaches:
        total[r][c] += distance
        reach[r][c] += 1

answer = min(total[r][c] for r, c in empty cells if reach[r][c] == buildings)

Two grids, not one. total alone is a trap: a cell walled off from one building never accumulates that building's distance, so it looks cheap. Requiring reach == buildings is the correctness condition, and if no cell satisfies it the answer is -1.

4. A 30-second worked example (snakes and ladders)

A 2×2 board, [[-1,-1], [-1,3]]. Squares are numbered from the bottom-left, snaking:

board rows:      row 0:  -1  -1        squares 4  3      (right to left)
                 row 1:  -1   3        squares 1  2      (left to right)

start at square 1
roll 1 → square 2, whose cell is board[1][1] = 3 → jump to square 3
roll 2 → square 3 directly
roll 3 → square 4 = n*n → done in 1 move

One move suffices, because square 4 is within a single roll of the start. The instructive part is the numbering: square 2 is at board[1][1] and square 3 at board[0][1], which is not what a naive divmod gives you — the rows run bottom-up and every other one runs right-to-left.

5. Where you'll actually meet this

• Puzzle and game solvers. Any "fewest moves" question over configurations is a BFS on an implicit graph.
• Robotics and path planning. State spaces of position plus orientation plus held-item, generated rather than stored.
• Facility location. Choosing a site minimising total travel to several fixed points is the buildings problem, unchanged.
• Version and state migration. Fewest steps between two system configurations, with forbidden intermediate states as deadends.
• Network provisioning. Placing a cache or relay to minimise aggregate hop count to all clients.

6. Problems in this chapter

▶ Open the Lock

Fewest turns from "0000" to a target, avoiding deadends. Generate the eight neighbours of each code and BFS.
Pattern: BFS over an implicit state space. Target: O(10⁴ × 8) — bounded by the space, not the input.

▶ Snakes and Ladders

Fewest rolls to the final square. Convert the snaking numbering to coordinates, then BFS over squares with up to six moves each.
Pattern: BFS + a coordinate transform. Target: O(n²) time and space.

▶ Shortest Distance from All Buildings

The empty cell minimising total distance to every building. BFS from each building, accumulating distance and reach counts.
Pattern: multi-source accumulation. Target: O(buildings × mn) time, O(mn) space.

7. Common pitfalls 🚫

• BFS from the candidate cells instead of the buildings, which multiplies the work by the number of empty cells.
• Skipping the reach count. A cell that cannot see every building must be excluded, however cheap it looks.
• Not checking "0000" against the deadends before starting the search.
• Getting the wrap wrong. % 10 handles both 9 → 0 and 0 → 9; a subtraction without it goes negative.
• Mis-deriving the board numbering. It starts at the bottom row and alternates direction — verify on a 2×2 before writing the search.
• Rolling again after a ladder. The jump replaces the move; it does not extend it.
• Marking the pre-jump square as visited instead of the destination, which admits states twice.

8. Key takeaways

1. The neighbour function is the model. Once it is right the BFS is boilerplate.
2. Implicit graphs are generated, never stored — which is why a 10,000-state search is cheap.
3. Search from the few, not the many. One BFS per building beats one per candidate cell.
4. Two accumulators beat one when a cell must be both close and reachable.
5. Coordinate transforms deserve a hand-check on the smallest possible input.
6. Blocked states are just states never enqueued — no extra machinery.
7. Why interviewers like it: everyone knows BFS, so the question is whether you can see the graph that was never handed to you.

Order: Open the Lock → Snakes and Ladders → Shortest Distance from All Buildings.