Walls and Gates — BFS from every gate at once
Start the search from all gates simultaneously and expand outward one ring at a time. The first ring to reach a room is, by construction, its shortest distance to any gate.
Try:
← Prev
Next →
▶ Play
Reset
gate (0)
wall
empty room (∞)
distance filled