Grid traversal
A board of cells is a graph you never have to build: each cell's neighbors are the cells next door. Flood fill finds regions, and BFS finds the fewest steps, from one start or from many at once.
A grid is a graph whose neighbors are the cells next door
A board of cells, a map of land and water or a maze is a graph that is never written down. Each cell is a node, and its neighbors are the cells next to it: four (up, down, left, right), or eight if diagonal moves count. You don't build an adjacency list; you compute the neighbors on the spot by adding a direction to the row and column.
Everything from BFS & DFS then carries over. DFS (often recursive) answers "which cells are joined to this one?"; BFS answers "how many steps away?". The grid itself is usually the record of what's been visited: overwrite a cell when you reach it.
The rule
Treat each cell as a node and the cells next door as its neighbors. Check the bounds before you read a cell, mark a cell when you first reach it, and every cell is handled once: O(rows × columns).
Boards, regions and "fewest moves" point here
A board of cells with islands, regions, rooms or walls
Each cell is a node; its neighbors are the cells next door
Count or measure joined regions
Loop over every cell and flood fill each one not yet visited
Fewest steps, moves or minutes across a board
BFS from the start; the first time you reach a cell is the fewest steps
Something spreads from several places at once (rot, fire, the nearest exit)
Multi-source BFS: every source starts in the queue
Cells touching the border behave differently
Flood fill from the border first, then deal with the rest
Flood fill: repaint every cell joined to the start
Flood fill is DFS on a grid: paint a cell, then call yourself on its four neighbors. A call returns at once if it is off the board or the cell isn't the old color, and a painted cell no longer has the old color, so nothing is painted twice.
The same few lines count islands (flood each unvisited land cell and add one) or measure their areas (count the cells each flood paints).
Many starting points: put them all in the queue at once
Rot spreads one cell per minute from every rotten orange at the same time. Running BFS from each rotten orange separately would repeat the work. Instead, start with all of them in the queue together: multi-source BFS. The waves then grow from every source at once, and each fresh orange is reached by the nearest rotten one.
Here the BFS goes a whole wave at a time (one list per minute) so the minutes are easy to count.
Multi-source BFS solves every "distance to the nearest X" problem on a board: the nearest 0, the nearest exit, the nearest land. Put every X in the queue first.
Shortest route with eight directions
Now the moves include diagonals, and the answer is the fewest cells on a route. It is plain BFS from one corner with eight directions instead of four, and a grid of route lengths that doubles as the visited record. Because cells leave the queue in order of distance, the corner's route length is final once it comes out of the queue, and the search can stop there.
The shape to reuse
- 1dirs ← [[1, 0], [−1, 0], [0, 1], [0, −1]]
- 2queue ← every starting cell, each marked
- 3while the queue isn't empty
- 4 [r, c] ← take the front of the queue
- 5 for each d in dirs
- 6 nr ← r + d[0]; nc ← c + d[1]
- 7 if nr, nc is inside the grid, open and not marked
- 8 mark it (and store its distance)
- 9 append [nr, nc] to queue
For regions without distances, the recursive form is shorter: check the bounds and the cell, mark it, recurse in each direction.
Where grid searches go wrong
Check r and c against the bounds before reading grid[r][c], and in that order.
Mark a cell when it enters the queue, not when it leaves. Otherwise the same cell is queued by several neighbors.
A 1,000 × 1,000 grid of one color makes a flood fill a million calls deep and overflows the call stack. Use BFS or your own stack there.
Count a wave only when it reaches something new, or the last, empty wave adds a minute.
Read the problem: diagonals change both the neighbors and the answer.
Painting the grid in place is the cheap visited record, but say so, or copy it, when the caller still needs the original.
3 questions
Remember this
- A grid is a graph you never build: a cell's neighbors are the cells next door, found by adding a direction.
- Flood fill (DFS) finds and measures regions; BFS finds the fewest steps, and multi-source BFS starts from every source at once.
- Check the bounds before reading a cell and mark it when it enters the queue, so each cell is handled once: O(rows × columns).
Now solve some yourself
Only this topic 0 of 17 solved
- EasyFence around an island
- EasyCount the rooms in a floor plan
- MediumCount the islands
- MediumShortest way through a labyrinth
- MediumThe longest shortest walk in a maze
- MediumThe biggest island
- MediumLand cells that can't walk off the board
- MediumIslands that don't touch the border
- MediumCapture regions that are fully surrounded
- MediumIslands in one grid that sit inside islands of another
- MediumCells where water reaches both oceans
- MediumDistance from every cell to the nearest 0
- MediumThe water cell farthest from any land
- MediumNearest way out of a maze
- MediumShortest bridge between two islands
- HardFewest steps when you may break k walls
- HardEscape a maze before the monsters reach you
Mixed with topics you have practiced 0 unlocked
1 more once you have practiced Hash tables & maps. Play one of its examples to the end and solve one of its problems to unlock them.
Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.
Next