Flood fill in Python

Why this matters

A paint program has a bucket tool. You click one pixel, and every pixel that touches it in the same colour changes too. A game uses the same idea to find which map tiles a character can reach, and a photo app uses it to select a shape. The method behind all of these is called flood fill. It is short, it is recursive, and it shows a real limit of recursion: Python allows only a fixed number of waiting calls, and a large grid can use all of them.

Earlier lessons in this module covered the base case and the call stack. Here you use both on a grid, which has two dimensions instead of one.

What a grid is

A grid is a table of cells with rows and columns. In Python, a grid of numbers is a list of rows, and each row is a list of numbers:

grid = [
    [1, 1, 0],
    [0, 1, 0],
]

This grid has two rows and three columns. The cell in row 0, column 1 holds 1, and you read it with grid[0][1]. Rows are numbered from 0 to len(grid) - 1. Columns are numbered from 0 to len(grid[row]) - 1. In this example len(grid) is 2 and len(grid[0]) is 3.

Call a cell open when its value is 1 and blocked when it is 0. Two open cells are connected when you can walk from one to the other by steps up, down, left or right, and every cell on the way is open. Diagonal steps do not count here. A region is a group of open cells that are all connected to each other and to no other open cells.

In the grid above, the cells in row 0 columns 0 and 1 and the cell in row 1 column 1 are connected, so they form one region of three cells. The cell at row 1 column 0 is blocked, and the cell at row 0 column 2 is blocked too.

The idea, one step at a time

Picture a person standing on a tile in a field. The rule is simple:

1. If the tile is outside the field, or it is blocked, or the person has already painted it, do nothing and stop.
2. Otherwise paint the tile.
3. Then walk to each of the four neighbours, one after another, and repeat from step 1 at each one.

This is depth-first search, which means the search goes as far as it can down one path before it comes back to try another. The painted tiles are the region.

The rule has three checks at the start (outside, blocked, already painted) and then the work. Those three checks are the base cases. The recursive case is the four neighbour calls. The mark must come before the four calls. If the tile is marked only after them, the neighbours can call back into this tile before it is marked, and the calls never end.

Here is the complete labelling program. It finds every region in a small grid and gives each region its own number:

Press Run. The output is:

1 1 0 0 2
1 0 0 2 2
0 0 3 0 0
4 0 3 3 3
regions: 4

The outer loops look at every cell. When a cell is open and has no label yet, it starts a new region, so next_label goes up by one and fill paints everything connected to that cell with the new number. Cells that are already labelled are skipped, so each region is painted exactly once. The four regions are the top-left group of three cells labelled 1, the group of three on the right labelled 2, the group of four in the middle and bottom labelled 3, and the single cell at the bottom left labelled 4.

Notice the grid is never copied. The same labels list is shared by every call, because a list is changed in place when you assign to one of its items. Copying it on each call would make the work much slower.

Tracing a small grid by hand

The labelling program is hard to follow on a big grid, so take a grid of two rows and two columns:

1 1
0 1

The program starts at row 0, column 0 and writes out each call. A version of the same function that prints a line for every call shows the order of the work:

The output is:

fill(0, 0)
  labelled
  fill(-1, 0)
    off grid, stop
  fill(1, 0)
    blocked, stop
  fill(0, -1)
    off grid, stop
  fill(0, 1)
    labelled
    fill(-1, 1)
      off grid, stop
    fill(1, 1)
      labelled
      fill(0, 1)
        already labelled, stop
      fill(2, 1)
        off grid, stop
      fill(1, 0)
        blocked, stop
      fill(1, 2)
        off grid, stop
    fill(0, 0)
      already labelled, stop
    fill(0, 2)
      off grid, stop
[[1, 1], [0, 1]]

Read the output as a tree. The call for row 0, column 0 labels its own cell first, then makes its four calls in order: up, down, left and right. Up and left are off the grid. Down is blocked. Right reaches row 0, column 1, which is open, so the search goes deeper. From there the call for row 1, column 1 is reached by going down. Its call back up to row 0, column 1 finds the cell already labelled and stops. That check is what keeps the search finite. When every call has returned, the labels hold the one region of three cells.

The indentation in the output is the depth of the call. The deepest labelling call is fill(1, 1), 2 levels below the first one, so at that moment three calls are on the stack: the first call, the one for row 0, column 1, and the one for row 1, column 1.

Second example: measuring a region

Often you need a number, not a picture. This version returns the size of the region that contains a starting cell. The map uses . for open and # for blocked, so the code reads like the picture it describes. Each row is a list of single characters, which lets the function change one cell at a time.

The output is:

size from (0, 0): 3
size from (2, 2): 8
size from (2, 2) again: 0
#####
#####
#####
#####

Each call returns 1 for its own cell, plus the sizes that its four neighbour calls return. A neighbour that is outside the map, or blocked, or already painted, returns 0. So the total is the number of cells that the search reaches.

The second call from (2, 2) returns 0 because the first call turned every cell of that region into #. The painted cell acts as a "done" flag. The final picture is all # because every open cell was reached by one of the two starts.

The return value in this function is the total of the four calls. A function that returns a value and calls itself this way is written the same way as the sum of a list in the arrays and strings lesson, with the total built up as the calls return. The backslash at the end of the return line joins it to the next line. Inside brackets Python joins lines on its own, so the backslash is only needed here because the expression is not in brackets.

Third example: how deep the stack gets

Every call that has not yet returned keeps a frame on the call stack. The frame holds the parameters and local variables of that call. Python limits the number of frames that can wait at the same time. The limit is 1000 by default, which you saw in the first lesson. When a recursion needs more than that, Python raises RecursionError and stops the call.

For a flood fill, the depth can be much larger than the size of the region. The search goes down one path until it hits an edge, and every step on that path is a waiting call. The depth test below counts the deepest call it reaches. It fills a grid made only of open cells, first as a square and then as a single row, which is called a strip here. The seen set holds the cells already painted. A set is a collection of unique values with fast membership tests, and (row, col) is a tuple, a fixed pair of values written in brackets, which can be a set item.

Press Run. On Python 3.14 with the default limit, the output was:

limit: 1000
10 x 10 open grid: filled, max depth 101
20 x 20 open grid: filled, max depth 401
30 x 30 open grid: filled, max depth 901
40 x 40 open grid: RecursionError
1 x 100 strip: filled, max depth 101
1 x 500 strip: filled, max depth 501
1 x 900 strip: filled, max depth 901
1 x 1000 strip: RecursionError
1 x 30000 strip: RecursionError

The strip is the clearest case. Start at the only cell. The search tries up and down, which are off the grid, so those calls return at once. Then it tries left, which is also off the grid, and then right, which is the next cell. That call does the same thing again. So each cell adds one more waiting call, and a strip of 1000 cells needs about 1000 frames at once, plus the frames already in use. The test printed RecursionError for 1000 cells, and it filled 900.

The square grids show the same effect in a less obvious way. A 30 by 30 grid reached a depth of 901, because the search walked through every cell in one long path before it came back. The depth grows with the length of the path the search takes, and that path can be much longer than the side of the grid.

The limit is not a property of the algorithm. It is a property of the interpreter's settings. sys.setrecursionlimit can raise the limit, and a larger limit lets the same program fill the bigger grids. But Python's own stack is finite too, and a limit set too high can crash the interpreter instead of raising an error. A raised limit only moves the problem. A 1000 by 1000 grid of open cells can have a region with a million cells, so the depth can reach a million. The lesson for a grid of any real size is to avoid recursion for flood fill and use an explicit stack. The explicit stack lesson later in this module shows how to do that with a list that you manage yourself.

Common mistakes

Forgetting the visited check

If the program does not mark cells, the search goes back and forth between two cells forever. Here is a version with no marking:

grid = [[1, 1], [1, 1]]
 
 
def fill(row: int, col: int) -> None:
    if row < 0 or row >= len(grid):
        return
    if col < 0 or col >= len(grid[0]):
        return
    if grid[row][col] != 1:
        return
    fill(row - 1, col)
    fill(row + 1, col)
    fill(row, col - 1)
    fill(row, col + 1)
 
 
fill(0, 0)
print("done")

Running it prints the first lines of a long traceback, and the program stops. The output ends like this, with the repeated frames cut short:

Traceback (most recent call last):
  File "nomark.py", line 17, in <module>
    fill(0, 0)
    ~~~~^^^^^^
  File "nomark.py", line 12, in fill
    fill(row + 1, col)
    ~~~~^^^^^^^^^^^^^^
  File "nomark.py", line 11, in fill
    fill(row - 1, col)
    ~~~~^^^^^^^^^^^^^^
  File "nomark.py", line 12, in fill
    fill(row + 1, col)
...
    fill(row - 1, col)
    ~~~~^^^^^^^^^^^^^^
RecursionError: maximum recursion depth exceeded

The cell at row 0, column 0 calls the cell below it, which calls back up to row 0, column 0. Nothing ever changes, so no call ever ends. The fix is to change the cell as soon as it is visited and to check that change before the four calls. The file name and line numbers in your output depend on where you saved the file.

Forgetting the lower bound

The check row < 0 is easy to leave out, because the other checks look similar. Python makes this worse than most languages. A row of -1 is not an error, because Python counts negative indexes from the end of a list. So grid[-1] is the last row, and the search goes to the bottom of the grid instead of stopping. The next call goes to -2, which is the second-last row, and the search keeps walking backwards through the grid. Here is the same program as before, with the check for row < 0 removed:

grid = [[1, 1, 0], [1, 1, 0]]
labels = [[0] * 3 for _ in range(2)]
 
 
def fill(row: int, col: int) -> None:
    if row >= len(grid):
        return
    if col < 0 or col >= len(grid[0]):
        return
    if grid[row][col] != 1 or labels[row][col]:
        return
    labels[row][col] = 1
    fill(row - 1, col)
    fill(row + 1, col)
    fill(row, col - 1)
    fill(row, col + 1)
 
 
fill(0, 0)
print(labels)

The search walks upward through the list, and it ends with an error once the row goes past the start of the list. The last lines of the output are:

  File "nobound.py", line 10, in fill
    if grid[row][col] != 1 or labels[row][col]:
       ~~~~^^^^^
IndexError: list index out of range

The error appears late, far from the cause. The fix is the check row < 0, placed with the other bounds checks. When you write a grid search in Python, check both ends of every index.

Using the wrong bounds check

The check must be row >= len(grid), not row > len(grid). A row equal to len(grid) is one past the last row, so it does not exist. Here is a version with the wrong comparison:

grid = [[1, 1], [1, 1]]
 
 
def fill_wrong_bound(row: int, col: int) -> None:
    if row < 0 or row > len(grid):
        return
    if col < 0 or col >= len(grid[0]):
        return
    if grid[row][col] != 1:
        return
    grid[row][col] = 2
    fill_wrong_bound(row + 1, col)
    fill_wrong_bound(row, col + 1)
 
 
fill_wrong_bound(0, 0)
print("done")

The output is:

Traceback (most recent call last):
  File "wrongbound.py", line 16, in <module>
    fill_wrong_bound(0, 0)
    ~~~~~~~~~~~~~~~~^^^^^^
  File "wrongbound.py", line 12, in fill_wrong_bound
    fill_wrong_bound(row + 1, col)
    ~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^
  File "wrongbound.py", line 12, in fill_wrong_bound
    fill_wrong_bound(row + 1, col)
    ~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^
  File "wrongbound.py", line 9, in fill_wrong_bound
    if grid[row][col] != 1:
       ~~~~^^^^^
IndexError: list index out of range

Python reports the bad index only when the program reads the cell. The check that should have stopped the call did not stop it. When you see this message, look at the bounds checks above the line named in the error.

Assuming a bigger grid will work because a small one did

A 30 by 30 grid filled in the depth test above, but a 40 by 40 grid did not. The code is the same in both cases. The depth grows with the length of the path the search takes, not with the number of cells, so a small test can pass and a real map can fail. Test with a grid shaped like your real data, or with a large open grid, before you trust the code.

Using the four directions when the problem says eight

The program moves up, down, left and right only. A problem that says "touching, including corners" needs eight directions. The count of a region can change a lot. The practice exercises show both versions.

Practice

Exercise 1

Use the map from the second example, with . for open and # for blocked, and this starting map:

..#..
.##..
#...#
##.##

On a fresh copy of this map, what does region_size return when it starts at row 3, column 2?

Show the answer

The answer is 8. The cell at row 3, column 2 is open, and its neighbour above it, row 2 column 2, is open. That cell belongs to the group of 8 cells that also contains row 2 column 2 in the second example, so the search returns 8.

Exercise 2

Write a function count_regions that counts how many separate regions of open cells a map contains. Use region_size, and make sure your function works on a copy of the map so the original is kept.

Show the answer

def count_regions(m: list[list[str]]) -> int:
    regions = 0
    for r in range(len(m)):
        for c in range(len(m[r])):
            if m[r][c] == ".":
                regions += 1
                region_size(m, r, c)
    return regions
 
 
area = [list(row) for row in MAP]
print(count_regions(area))  # 2

This function changes m as it goes, so it must be called with a copy, as the last two lines show. On the map from the second example, it returns 2. The region at the top left has 3 cells, and the region on the right and in the middle has 8 cells.

Exercise 3

Write region_size8, which counts the region the way region_size does, but also moves diagonally. Use two nested loops for the eight neighbours, and skip the offset of 0 and 0, which is the cell itself. Find the size from row 0, column 0 on the map in Exercise 1.

Show the answer

def region_size8(m: list[list[str]], row: int, col: int) -> int:
    if row < 0 or row >= len(m):
        return 0
    if col < 0 or col >= len(m[row]):
        return 0
    if m[row][col] != ".":
        return 0
    m[row][col] = "#"
    total = 1
    for dr in (-1, 0, 1):
        for dc in (-1, 0, 1):
            if dr != 0 or dc != 0:
                total += region_size8(m, row + dr, col + dc)
    return total

With diagonal steps, the open cells on that map join into one region. The size from row 0, column 0 is 11, which is every open cell on the map. The earlier count with four directions split them into 3 and 8.

Exercise 4

Write same_region(m, r1, c1, r2, c2), which returns True when the open cells at the two positions are in the same region and False otherwise. It must not change the map it is given.

Show the answer

def copy_map(m: list[list[str]]) -> list[list[str]]:
    return [row[:] for row in m]
 
 
def same_region(m: list[list[str]], r1: int, c1: int, r2: int, c2: int) -> bool:
    if m[r1][c1] != "." or m[r2][c2] != ".":
        return False
    c = copy_map(m)
    region_size(c, r1, c1)
    return c[r2][c2] == "#"

The copy_map function makes a new list of rows, and each row is copied with row[:], so flood fill only changes the copy. The function returns True for row 0, column 0 and row 1, column 0 on the map in Exercise 1, and False for row 0, column 0 and row 0, column 3, because those two cells are in different regions.

Exercise 5

A grid has 30000 open cells in one row and no other open cells. Without running the code, say whether the depth test above would reach it on the default settings, and give the reason. Then say what would change the answer, and what the safe choice is for a real grid.

Show the answer

On the default settings it would not reach it. The strip of 1000 cells already raised RecursionError, so a strip of 30000 cells would also fail. The reason is that each cell adds one waiting call, so the depth grows with the length of the strip. Raising the limit with sys.setrecursionlimit can allow longer strips, but a limit set too high can crash the interpreter. For a real grid, use an explicit stack, as the explicit stack lesson shows.

Summary

• Flood fill marks every open cell connected to a starting cell, using a recursive search that tries up, down, left and right.
• Check the bounds, check that the cell is open and check that it is not yet marked before any recursive call, and mark the cell before the four calls.
• A function that returns a count adds 1 for its own cell and the counts from its four neighbour calls.
• The depth of the search can be much larger than the size of the region, because the search follows one long path first.
• A RecursionError means the chain of waiting calls went past the limit. Raising the limit only moves the problem, so large grids need an explicit stack.
• Python counts negative indexes from the end of a list, so a missing row < 0 check does not fail at once. Check both ends of every index.