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 two accumulator grids.
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 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 some 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 ofO(cells × mn).
🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core 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 why a 10,000-node search stays cheap.
1. A state that is a string
seen = set(deadends) # deadends are pre-marked, never entered
if "0000" in seen: return -1 # blocked start: no turn is possible
if target == "0000": return 0
seen.add("0000")
q = deque([("0000", 0)])
while q:
s, d = q.popleft()
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 in seen: continue
if t == target: return d + 1
seen.add(t); q.append((t, d + 1)) # mark on push, not on pop
return -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. Check "0000" against them before the loop: a blocked start means -1, and if the target is "0000" the answer is 0.
Marking on push means each state enters the queue once, so the cost is O(10^4 * 8 * 4) time (8 neighbours, 4 characters per string build) and O(10^4) space. Marking on pop is also correct but lets duplicates pile up in the queue, up to 8 times as many entries.
The whole space is 10,000 states, so the search is bounded no matter how the input looks. With no deadends the distance is the sum over dials of min(d, 10 - d), so the farthest state from 0000 is 5555, at 20 turns.
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: a jump is taken once per move, never chained. Apply the jump first, then mark the destination as seen rather than the square you rolled to. Marking the wrong one produces answers that are almost right. Every move is one roll, so plain BFS gives the fewest rolls in O(n^2) time and space.
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. Buildings block movement just like obstacles do, so [[1,1],[1,0]] gives -1: the empty cell touches two buildings, but the third can only be reached by walking through one. Each building's BFS touches every cell at most once, so the total is O(buildings * m * n) time and O(m * n) space.
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:
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, marking states when you push them.
Pattern: BFS over an implicit state space. Target: O(10^4 * 8 * 4) time and O(10^4) space, 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. Buildings and obstacles both block.
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.
% 10handles both9 -> 0and0 -> 9in Python, but in Java, C++ and JavaScript(0 - 1) % 10is-1. Use(d + 9) % 10for the downward turn. - Mis-deriving the board numbering. It starts at the bottom row and alternates direction, so 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.
- Letting a building be walked through in the buildings problem. It is a wall, not a road.
8. Key takeaways
- The neighbour function is the model. Once it is right the BFS is boilerplate.
- Implicit graphs are generated, never stored, which is why a 10,000-state search is cheap.
- Search from the few, not the many. One BFS per building beats one per candidate cell.
- Two accumulators beat one when a cell must be both close and reachable.
- Coordinate transforms deserve a hand-check on the smallest possible input.
- Blocked states are just states never enqueued, no extra machinery.
- 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.
Open the lock
Core idea: Never build the graph. A state is the four-digit string on the dials, and its eight neighbours are made on demand by turning each wheel one notch up or down, with
% 10handling the wrap. Put the deadends in theseenset before the search starts so the search can never enter them, and check"0000"against them first: a blocked start means-1. There are only 10,000 states, so BFS does at most 10,000 x 8 neighbour builds whatever the input.
Problem, rephrased
You are testing a four-wheel combination padlock. Each wheel shows a digit 0 to 9, and turning it one notch moves it to the next digit, wrapping from 9 to 0 and from 0 to 9. The lock starts at "0000". A test rig has a list of deadends: if the display ever shows one of those codes, the wheels jam and the lock cannot be opened any more. The lock opens when the display shows target.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson