Flood fill

From Algorithmist
(Redirected from Flood Fill)
Jump to navigation Jump to search

A technique reminiscent of "paintbrush"-type programs. Given a (usually rectangular) grid, you want to replace the colour of a connected region with another colour.

For example, if you flood fill the top-right square of

GRRR
BGRR
RGBB

with the colour P, then the result would be

GPPP
BGPP
RGBB

You usually use depth-first or breadth-first search to do this. Be aware that the recursion depth in DFS can sometimes be too large.

Of course the same technique applies to graphs.