Flood Fill
Matrix & Grid: lesson 5 of 5
Spread while the colour matches, stop the moment it does not.
Lesson 5 of 5 · 4 min
Flood Fill
Step 1 of 9
A paint bucket: click one cell and the connected patch sharing its colour becomes the new one.
The Idea
Click a cell, remember the colour under it, and repaint. Then ask the four neighbours the same question: are you that colour too?
Each match repaints and passes the question on, so the patch grows outwards until every edge is a different colour or the grid's own border. Cells already repainted no longer match, which is what stops the spread from looping.
Real-World Example
It is the paint bucket in every image editor, the "select similar region" tool, and how Minesweeper opens a whole empty area from one click. Level editors use it to detect enclosed rooms before a player can walk into one.
The Code
def flood(canvas, r, c, new):
start = canvas[r][c]
if start == new: # already that colour: nothing to do
return canvas
stack = [(r, c)]
while stack:
y, x = stack.pop()
if not (0 <= y < len(canvas) and 0 <= x < len(canvas[0])):
continue # off the grid
if canvas[y][x] != start:
continue # a wall, or already repainted
canvas[y][x] = new
stack += [(y-1, x), (y+1, x), (y, x-1), (y, x+1)]
return canvas
print(flood([["A", "A", "B"],
["A", "A", "B"],
["B", "A", "B"]], 1, 0, "C"))
# [['C', 'C', 'B'], ['C', 'C', 'B'], ['B', 'C', 'B']]Your turn
What does this print?
print(flood([['A', 'B'],
['B', 'A']], 0, 0, 'C'))Mini quiz
1 / 3