Flood fill

O(cells)

Flood fill colours a connected region: starting from one cell it spreads to each open 4-connected neighbour, and theirs in turn, stopping only at walls and the grid edge. It's exactly breadth-first search without a goal — it keeps going until the entire reachable region is filled. The same idea powers the paint-bucket tool, revealing blank areas in Minesweeper, and counting connected regions in an image. It visits each cell once, so it runs in time linear in the number of cells. (A depth-first or recursive version fills the same region in a different order.)

Click a cell to toggle a wall
Grid
Edit the input and press Play

How it works

  1. Start from the seed cell and mark it to be filled.
  2. Spread to each open neighbour that hasn't been seen yet.
  3. Keep going outward, never crossing a wall or the edge.
  4. Stop when the whole connected region has been filled.

Pseudocode

1floodFill(grid, start):              # O(cells)2  queue ← [start]; seen ← {start}3  while queue not empty:4    cell ← queue.dequeue()5    fill cell6    for nbr in open neighbours(cell):7      if nbr not seen:8        seen.add(nbr); queue.enqueue(nbr)9  # the whole connected region is filled