Grid flood fill and island counting in Python

Why this matters

A paint bucket tool fills a region of one colour with another colour. A Minesweeper game opens every empty square next to the one you click, and keeps opening until it reaches squares that touch a mine. A satellite photo of land and water can be turned into a grid, and you may need to know how many separate pieces of land it shows. All three tasks ask the same question: starting from one cell, which other cells can you reach by moving from neighbour to neighbour?

This lesson answers that question with the two search methods from the earlier graph lessons, depth-first search (DFS) and breadth-first search (BFS). The grid is a special kind of graph, so the same methods apply without any change in their logic. The lesson uses only Python and the standard library module collections.

A grid is a graph

A graph is a set of nodes joined by edges. A node is a single thing, and an edge is a link between two nodes. In a grid, each cell is a node. Two cells are joined by an edge when they are neighbours, meaning one is directly above, below, left or right of the other. A cell has at most four neighbours, and the corner cells have only two.

Here is a small grid written as a Python list of lists. Each row is a list of single characters, where 1 means land and 0 means water. The rows are the first index and the columns are the second index, so grid[r][c] is the cell in row r and column c:

grid = [
    list("11000"),
    list("11000"),
    list("00100"),
    list("00011"),
]

list("11000") makes a list with one character in each item, so the first row is ['1', '1', '0', '0', '0']. A Python string cannot be changed in place, so each row is a list. The number of rows is len(grid). The number of columns in row r is len(grid[r]).

The four neighbour moves are stored as pairs. The first number in a pair is the change in row, and the second is the change in column. Move 0 goes up, move 1 goes down, move 2 goes left and move 3 goes right.

DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

To visit the neighbours of cell (r, c), add the change in row and the change in column for each move. Some of the results fall outside the grid, so every move needs a bounds check. A bounds check is a test that the row and column are still inside the grid before you read from it.

def inside(grid, r, c):
    return 0 <= r < len(grid) and 0 <= c < len(grid[r])

The check uses len(grid[r]) for the column limit, so it still works when rows have different lengths. The first comparison is written as 0 <= r < len(grid), which Python reads as 0 <= r and r < len(grid) joined together.

Flood fill with recursion (depth-first search)

A flood fill takes one starting cell and a target colour. It changes every cell that has the target colour and is connected to the start, and leaves other cells alone. Think of pouring water onto one spot of a floor: the water spreads over every connected patch of the same tile and stops at the edges.

A depth-first search goes as far as it can down one path before it turns back. The easiest way to write one in Python is with recursion, which means a function that calls itself. Each call handles one cell, then calls itself for each neighbour.

Here is the idea written as a function:

def fill_dfs(grid, r, c, target, replacement):
    if not inside(grid, r, c) or grid[r][c] != target:
        return
    grid[r][c] = replacement
    for dr, dc in DIRECTIONS:
        fill_dfs(grid, r + dr, c + dc, target, replacement)

The first if is the stopping rule. If the cell is off the grid, or it does not have the target colour, the function returns at once and does nothing. The second line paints the current cell. The loop then asks each neighbour to do the same job.

Take this three-by-three grid of letters, with a flood fill starting at the top-left cell and target A:

AAB
ABB
AAA

The call starts at (0, 0). It paints that cell, then calls itself for the cell above (off the grid, so it stops), the cell below (1, 0), the cell to the left (off the grid), and the cell to the right (0, 1). The call for (1, 0) paints it, then calls for (2, 0), which paints it and calls for (2, 1), and so on. The path goes down the left column, then right along the bottom row. When a branch reaches a dead end, its calls return one by one, and the caller tries its next neighbour. Each cell is painted exactly once.

The result, from the program at the end of this lesson:

before fill:
  AAB
  ABB
  AAA
after DFS fill from (0, 0):
  XXB
  XBB
  XXX

Cell (1, 1) stays B, because the fill only paints cells that have the target colour A. The cell is surrounded by A cells on three sides, but it is not A, so it is never painted.

Flood fill with a queue (breadth-first search)

A breadth-first search visits cells in rings. It handles every cell one step from the start before it handles any cell two steps away, and so on. It uses a queue, which is a line where you add items at the back and take them from the front. The first item added is the first one taken.

Python provides deque in the collections module, which works as a queue. The method append puts an item at the back, and popleft removes the item at the front. The loop runs while the queue is not empty, which Python checks by testing the queue itself.

from collections import deque
 
def fill_bfs(grid, start_r, start_c, target, replacement):
    if grid[start_r][start_c] != target:
        return
    grid[start_r][start_c] = replacement
    queue = deque([(start_r, start_c)])
    while queue:
        r, c = queue.popleft()
        for dr, dc in DIRECTIONS:
            nr, nc = r + dr, c + dc
            if inside(grid, nr, nc) and grid[nr][nc] == target:
                grid[nr][nc] = replacement
                queue.append((nr, nc))

Each queue item is a tuple with two numbers, the row and the column. A tuple is a fixed group of values in parentheses, and it cannot be changed after it is made. The code paints a cell at the moment it is added to the queue, not when it is removed. This matters. If a cell were added and only painted later, two different cells could both add the same neighbour before it was painted, and that neighbour would sit in the queue twice. Painting on add means each cell enters the queue exactly once.

The result for the same grid is the same as the recursive version. Python compares two lists of lists by their contents, so dfs_grid == bfs_grid prints True when both fills produce identical grids. The main difference is where the work is stored. The recursive version keeps its pending steps on the call stack, which is a memory area that Python uses for function calls, and that area has a size limit. The queue version keeps its pending steps in a list that grows as needed. The next section shows what the limit means in practice.

Counting islands

An island is a group of land cells where each cell can reach each other cell by moving up, down, left or right. In the grid below there are three islands, because the top-left block, the single 1 in the middle and the bottom-right pair are not joined to each other:

11000
11000
00100
00011

The counting method is short. Scan every cell in order. When you find land, add one to the count, then flood fill that island and turn all its land into water. Turning the land into water means that the island is never found again, so it is never counted twice.

def count_islands(original):
    grid = copy_of(original)
    count = 0
    for r in range(len(grid)):
        for c in range(len(grid[r])):
            if grid[r][c] == "1":
                count += 1
                fill_bfs(grid, r, c, "1", "0")
    return count

The helper copy_of makes a copy of the input, so the caller's grid is not changed. Each row is copied with the slice row[:], which makes a new list with the same items. Copying only the outer list with grid[:] is not enough, because the copy would still share the row lists with the original. The section on common mistakes shows what goes wrong.

def copy_of(grid):
    return [row[:] for row in grid]

Here is what happens to the second grid above. The scan reaches (0, 0), which is land, so the count becomes 1. The fill covers (0, 0), (0, 1), (1, 0) and (1, 1), and turns them into water. The scan continues along row 0 and row 1, finds only water, and reaches (2, 2). That is land, so the count becomes 2, and the fill turns that single cell into water. Finally the scan reaches (3, 3), which starts the third island, and the fill also covers (3, 4). The count ends at 3.

Largest island by area

Sometimes you need the size of each island, not just the number. The area of an island is the number of land cells in it. A recursive function can count them. It returns 1 for the cell it is on and then adds the area of each neighbour that is land. The sum function adds up the values that a generator expression produces, and the expression below gives one value for each of the four moves:

def island_area(grid, r, c):
    if not inside(grid, r, c) or grid[r][c] != "1":
        return 0
    grid[r][c] = "0"
    return 1 + sum(island_area(grid, r + dr, c + dc) for dr, dc in DIRECTIONS)
 
def largest_island(original):
    grid = copy_of(original)
    best = 0
    for r in range(len(grid)):
        for c in range(len(grid[r])):
            best = max(best, island_area(grid, r, c))
    return best

The cell is turned into water before the neighbours are visited. This is what stops the recursion from going back to a cell it has already counted.

The program gives these results for the second grid:

islands in second grid: 3
largest island in second grid: 4

The largest island is the two-by-two block in the top-left, which has four land cells.

Islands that do not touch the edge

Sometimes the question is how many islands lie fully inside the map, so that none of their land touches the border. The idea is to remove first every island that touches the border, and then count what is left. Any land cell on the border belongs to an island that touches the border, so a flood fill from each border land cell sinks all of those islands. The normal count then finds only the islands in the interior.

Here is a grid where the difference shows:

1110
1001
0110
0001

A plain count finds 4 islands. The top-left island touches the top edge. The single cell in row 1, column 3 touches the right edge. The single cell in row 3, column 3 touches the bottom edge. Only the pair in row 2, columns 1 and 2 touches no edge, so the answer for enclosed islands is 1.

def count_enclosed_islands(original):
    grid = copy_of(original)
    last_row = len(grid) - 1
    for r in range(len(grid)):
        for c in range(len(grid[r])):
            border = r == 0 or r == last_row or c == 0 or c == len(grid[r]) - 1
            if border and grid[r][c] == "1":
                fill_bfs(grid, r, c, "1", "0")
    return count_islands(grid)

The program prints these lines for the grid above:

all islands: 4
enclosed islands: 1
input unchanged: 1110

The copy at the top means the caller's grid is not changed, as in the earlier functions. The function calls count_islands, which makes its own copy of the already-sunk grid, so the cost is two copies of the grid. For a grid of a few thousand cells, that is not a concern.

Diagonal neighbours

The moves above count only up, down, left and right. A cell touching another cell only at a corner is not a neighbour in this lesson. This rule changes the answer. Take this grid, where each land cell touches the next one only diagonally:

10001
01010
00100

With the four moves in DIRECTIONS, the program prints islands in diagonal grid: 5. Each 1 is its own island. If a puzzle says that diagonal touches count, add the four diagonal moves to the list, which gives eight moves in total:

DIAGONAL_MOVES = [(-1, -1), (-1, 1), (1, -1), (1, 1)]
DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)] + DIAGONAL_MOVES

With those eight moves, the same grid has one island. Always check which rule the problem uses before you write the moves.

Running the whole program

This program has every function from the lesson in one file. It needs no input, so the site can run it. The output below is what it prints.

The output:

before fill:
  AAB
  ABB
  AAA
after DFS fill from (0, 0):
  XXB
  XBB
  XXX
DFS and BFS give the same grid: True
first row of second grid: ['1', '1', '0', '0', '0']
islands in second grid: 3
largest island in second grid: 4
second grid unchanged: 11000
all islands: 4
enclosed islands: 1
input unchanged: 1110
islands in diagonal grid: 5

Common mistakes

Missing the bounds check

A common first version of the recursive fill tests the colour before it tests the edges:

def fill_no_check(grid, r, c, target, replacement):
    if grid[r][c] != target:
        return
    grid[r][c] = replacement
    for dr, dc in DIRECTIONS:
        fill_no_check(grid, r + dr, c + dc, target, replacement)

Python handles this in two different ways, and neither is what you want. A row index that is too large raises an error. A negative row index does not raise anything. In Python, grid[-1] means the last row, grid[-2] the row before it, and so on. So a fill that moves up from the top row reads the bottom row, and it paints cells there that it should never reach.

Take the grid AB, BB, AA, with a fill from (0, 0) and target A. The correct result is XB, BB, AA, because only the top-left cell is A and connected to the start. The version above prints this instead, with no error message:

[['X', 'B'], ['B', 'B'], ['X', 'X']]

The bottom row was changed, because moving up from row 0 read row -1, which is row 2. The fix is the first line of fill_dfs, which checks the bounds before it reads the cell.

When a row index is too large, the error looks like this. Here the fill starts at the bottom row of an all-A grid, and it tries to move down past the last row:

    if grid[r][c] != target:
       ~~~~^^^
IndexError: list index out of range

Recursion that goes too deep

Each recursive call uses some space on the call stack. A fill over a large region can make a very deep chain of calls, with one call for every cell in the chain. Python limits the depth of this chain. The limit is 1000 by default, and you can read it with sys.getrecursionlimit().

On Python 3.14 with the default limit, a fill over a 30 by 30 grid of land finished, and a 40 by 40 grid failed with this error. The number in the middle line depends on the grid and on the path the fill took:

  [Previous line repeated 995 more times]
RecursionError: maximum recursion depth exceeded

Java reports the same problem as a StackOverflowError. Python can raise the limit with sys.setrecursionlimit, but a limit that is too high can crash Python itself. The fix is to use the queue version from the earlier section, which keeps its pending cells in a list and not on the call stack.

Replacing a colour with itself

If target and replacement are the same character, the cell still matches target after it is painted, so the recursion never stops:

same = [list("AAA")]
fill_dfs(same, 0, 0, "A", "A")

RecursionError: maximum recursion depth exceeded

Add a check at the top of the function that returns early when target equals replacement.

Reading the width of an empty grid

Some code reads the width from the first row before it looks at the number of rows:

grid = []
print(grid[0])

The grid has no rows, so grid[0] does not exist:

    print(grid[0])
          ~~~~^^^
IndexError: list index out of range

Check len(grid) == 0 first and return 0 for an empty grid.

Changing a character in a string row

A row written as a string cannot be changed in place. Python stops with this error:

rows = ["11000", "11000"]
rows[0][0] = "0"

TypeError: 'str' object does not support item assignment

Use list("11000") to make a row that can be changed, as the examples in this lesson do.

Copies that share rows

Two kinds of copy look like they make a new grid, but they do not. Multiplying a list copies references to the same inner list, so every row is the same object:

bad = [["."] * 3] * 3
bad[0][0] = "X"
print(bad)

[['X', '.', '.'], ['X', '.', '.'], ['X', '.', '.']]

The slice grid[:] makes a new outer list, but its rows are the same lists as before. A fill on the copy then changes the original:

original = [list("AB"), list("BB")]
shallow = original[:]
fill_dfs(shallow, 0, 0, "A", "X")
print(original)

[['X', 'B'], ['B', 'B']]

Use [row[:] for row in grid], as copy_of does, to copy each row as well.

Practice

Exercise 1. Count the islands in the one-row grid 10101. Each 1 is separated from the others by a 0.

Show the answer

There are 3 islands. Each land cell is alone, because the neighbours of every 1 are 0 or the edge of the grid.

Exercise 2. Count the water regions in the grid 101, 010, 101, using the same up, down, left and right rule. A water region is a group of 0 cells joined the same way.

Show the answer

There are 4 water regions. The four 0 cells are at (0, 1), (1, 0), (1, 2) and (2, 1). Each one touches only 1 cells on its up, down, left and right sides, so each forms its own region.

Exercise 3. Explain why fill_bfs paints a cell when it adds the cell to the queue, and what would happen if it painted the cell only when it removed it from the queue.

Show the answer

If a cell is painted only when removed, it can be added to the queue several times, because two different cells can each see it as unpainted and add it. The final grid is still correct, since the extra copies only repeat work. But the queue can grow much larger than the number of cells, which wastes memory and time on a big grid.

Exercise 4. Write a function island_size_at(grid, r, c) that returns the area of the island containing (r, c) without changing the caller's grid. Return 0 if the cell is water.

Show the answer

def island_size_at(grid, r, c):
    return island_area(copy_of(grid), r, c)

The copy keeps the caller's grid unchanged, and island_area already returns 0 for water and off-grid cells. On the second grid above, island_size_at(grid, 0, 0) returns 4, and island_size_at(grid, 0, 2) returns 0.

Exercise 5. For the grid 11000, 11000, 00100, 00011, list the islands in the order that the row-by-row scan finds them, and give the area of each.

Show the answer

The scan finds the top-left block first, at (0, 0), with area 4. Next it finds the single cell (2, 2), with area 1. Last it finds the pair starting at (3, 3), with area 2. The total is 3 islands, and the areas 4, 1 and 2 add up to 7, which equals the number of 1 cells in the grid.

Summary

• A grid is a graph where each cell is a node, and cells next to each other up, down, left or right are joined by an edge.
• A flood fill starts at one cell and changes every connected cell of the same colour, which DFS and BFS both do.
• The recursive DFS version is short but can hit Python's recursion limit on large grids, while the queue version keeps its pending cells in a list.
• To count islands, scan every cell, count each new piece of land once, and turn its land into water so it is not counted again.
• Always check bounds before reading a cell, because Python accepts negative indexes without an error, and check which neighbours the problem counts before you choose four moves or eight.