Flood Fill

Flood fill

Flood fill spreads from a starting cell to all connected cells sharing the same value, then changes them. It is the bucket tool in paint programs and the basis for region detection in grids and images.

How it spreads

Treat the grid as a graph where each cell connects to its neighbors, usually the four orthogonal cells.

• Remember the original color of the start cell.
• From the start, move to neighbors that still hold the original color.
• Recolor each visited cell to the new color so it is not processed again.
• Stop a branch when a neighbor is out of bounds or holds a different color.

You can drive the spread with BFS using a queue or DFS using recursion or a stack. Both reach exactly the cells in the connected region.

A common pitfall

If the new color equals the original color, a naive recursive fill can loop forever because cells never appear changed. Guarding against that case, or checking visited status separately, avoids the trap.

Key idea

Flood fill is a graph traversal over grid neighbors that recolors every connected cell sharing the start's original value.