Card 08/ 08
Recap: Grid Traversal
A grid is a graph you never build: breadth-first for distances, a fill from every unreached cell for regions, many sources at once for nearest.
A grid is a graph whose vertices are its open cells and whose edges join each cell to the cells beside it, computed with four offsets and a bounds check rather than stored. The question decides the search and where it starts:
| Question | Search | Start from | Mark when | Cost |
|---|---|---|---|---|
| Fewest moves between two cells | Breadth-first | The start | Added to the queue | O(R · C) |
| How many regions | Flood fill, any order | Every cell no fill has reached | Added to the stack | O(R · C) |
| Nearest of several sources, for every cell | Breadth-first | Every source at once, at distance 0 | Added to the queue | O(R · C) |
| Regions that do not reach the edge | Flood fill | Every open edge cell first, then the rest | Added to the stack | O(R · C) |
Marking a cell when it leaves the queue keeps the answer and lets the queue grow with the edges. Which neighbours count as joined, four or eight, changes how many regions a map holds, and a recursive fill on a large region can pass Python's recursion limit, so the fills here use a stack.
← → move through sections and cards