Flood fill

Why this matters

A grid is a picture made of cells. Each cell holds one character, and the rows of text make the picture. A paint bucket tool in an image editor fills the area around the spot you click. A game asks which rooms a player can reach from the door. A map program finds all the land that touches a coast. Each of these tasks starts at one cell and visits every cell you can reach by stepping from cell to cell. That task is called a flood fill, because the fill spreads outward the way water spreads across a floor.

The recursive version is short, and it reads almost like the task description. You mark the current cell, then ask the same question about each neighbour. This lesson builds the function step by step, runs it on small grids, and then measures how deep the recursion goes on a large grid. That measurement matters. Every recursive call uses memory on the call stack, and the stack has a fixed size. A grid that is too big can make the program crash even though the algorithm is correct.

Three terms are used throughout. A neighbour of a cell is the cell directly above, below, left or right of it. A region is a group of matching cells that can reach each other through neighbours. The call stack is the memory where the computer keeps track of functions that have started and not yet finished.

The idea

Take this small grid. A dot is open ground and a hash is a wall.

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

Start at row 0, column 0. That cell is open, so the fill marks it. Then the fill asks the same question about each of its four neighbours. The cell to the right is a wall, so that call stops at once. The cell below is open, so the fill marks it and asks about its neighbours, and so on. The walk keeps going as deep as it can before it turns back. This order is called depth-first search: go down one path as far as it goes, then come back and try the next path.

Each call follows four steps.

1. If the row or column is outside the grid, stop and count 0.
2. If the cell is not the kind we are filling, stop and count 0. This covers walls, and it also covers cells that were already filled.
3. Otherwise, change the cell to a mark, such as *. Count 1 for this cell.
4. Call the same function for the cell above, below, left and right. Add their counts to the count from step 3.

Steps 1 and 2 are the base cases. They answer without making any more calls. Every other call does the real work and then makes four more calls. Because a filled cell is never a target again, each cell can do this work only once.

The order in step 3 matters. The cell must be marked before the four calls are made. If it is marked after, a neighbour can look back, see the cell still open, and call it again. That loop is covered in the mistakes section.

Here is a count you can check by hand. Every call except the first is made by one filled cell, and each filled cell makes exactly four calls. If the fill marks F cells, then the total number of calls is 1 + 4 × F. For the grid above, the region that starts at the top-left cell has 6 cells, so there should be 25 calls in total. A counter that adds one to every call shows 25 calls for that grid.

Worked example 1: fill one region

The first program fills the region that contains the top-left cell of a bigger grid. It returns how many cells it filled.

The function takes the grid by reference, written vector<string>&. The & means the function works on the original grid, not a copy. Changing the cells in place is the point here, so a reference is the right tool. The open parameter says which character counts as open ground, so the same function can fill other kinds of cells later.

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
// Fills the region of cells equal to `open` that contains (r, c) with '*'.
// Returns how many cells this call filled, including the ones its calls filled.
int fill(vector<string>& grid, int r, int c, char open) {
    if (r < 0 || r >= (int)grid.size()) return 0;
    if (c < 0 || c >= (int)grid[r].size()) return 0;
    if (grid[r][c] != open) return 0;
 
    grid[r][c] = '*';
    int count = 1;
    count += fill(grid, r - 1, c, open);
    count += fill(grid, r + 1, c, open);
    count += fill(grid, r, c - 1, open);
    count += fill(grid, r, c + 1, open);
    return count;
}
 
void show(const vector<string>& grid) {
    for (const string& row : grid) cout << row << "\n";
}
 
int main() {
    vector<string> grid = {
        ".....#..",
        "..#.##..",
        "..#...#.",
        "####.#..",
        "......#.",
    };
 
    int filled = fill(grid, 0, 0, '.');
    cout << "filled from (0,0): " << filled << "\n";
    show(grid);
 
    vector<string> islands = {
        "##..#",
        "#...#",
        "..#..",
        "#.##.",
    };
    int count = 0;
    for (int r = 0; r < (int)islands.size(); ++r) {
        for (int c = 0; c < (int)islands[r].size(); ++c) {
            if (islands[r][c] == '#') {
                fill(islands, r, c, '#');
                ++count;
            }
        }
    }
    cout << "islands: " << count << "\n";
    show(islands);
}

Compile and run it with the warning flag turned on.

g++ -std=c++20 -Wall -o flood1 flood1.cpp
./flood1

The output is:

filled from (0,0): 20
*****#..
**#*##..
**#***#.
####*#..
******#.
islands: 4
**..*
*...*
..*..
*.**.

The first part shows the fill. Count the cells by row to check the 20. Row 0 has five open cells before the wall. Row 1 has three cells in the region. Row 2 has five, row 3 has one, and row 4 has six. Five plus three plus five plus one plus six is 20. The stars in the printed grid show exactly which cells were reached. The open cell at row 1, column 3 is reached through row 0, and the cell at row 3, column 4 is reached through row 2. The open cells in columns 6 and 7 are not reached, because the walls in column 5 and column 6 separate them from the rest.

The -Wall flag asks the compiler to report common mistakes. This program compiles with no warnings.

Worked example 2: counting islands

An island is a region of land that is cut off from other land by water. Here the hash is land and the dot is water. To count islands, you look at every cell in the grid. When you find land that is not yet marked, you have found a new island. Fill it, so every cell of that island is marked, and add one to the count. Because the fill marks cells, no island is counted twice.

The loop in main does exactly that. The fill function does not know it is counting islands. It only knows how to fill a region of one character. That separation is useful. The same fill can answer several questions with a small change to the loop around it.

The output marks the four islands with stars:

**..*
*...*
..*..
*.**.

The top-left island holds three cells: row 0 columns 0 and 1, and row 1 column 0. The top-right island holds two cells in column 4. The middle island holds three cells: row 2 column 2, and row 3 columns 2 and 3. The last island is the single cell at row 3, column 0. Row 3, column 1 is water, so that cell is cut off from the others.

The middle island is an L shape: one cell in row 2 sits above a pair of cells in row 3. Depth-first search follows every neighbour, so an L shape, a spiral or a blob all fill the same way.

Worked example 3: how deep the recursion goes

Every call that is still waiting for its neighbours stays on the call stack. Suppose the search walks down a long path, one cell after another, before it turns back. Then all those calls are waiting at the same time, one inside the other. The number of calls waiting at once is the depth. On a big open grid, the first path the search takes can wind through almost every cell. That makes the depth close to the number of cells.

The next program measures this. It fills a square grid of open cells and records the deepest level of calls it reaches. The grid size is read from the command line.

#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
int deepest = 0;
 
// Same fill as before, plus a record of the deepest level of calls reached.
int fill(vector<string>& grid, int r, int c, char open, int depth) {
    if (depth > deepest) deepest = depth;
    if (r < 0 || r >= (int)grid.size()) return 0;
    if (c < 0 || c >= (int)grid[r].size()) return 0;
    if (grid[r][c] != open) return 0;
 
    grid[r][c] = '*';
    int count = 1;
    count += fill(grid, r - 1, c, open, depth + 1);
    count += fill(grid, r + 1, c, open, depth + 1);
    count += fill(grid, r, c - 1, open, depth + 1);
    count += fill(grid, r, c + 1, open, depth + 1);
    return count;
}
 
int main(int argc, char** argv) {
    int size = argc > 1 ? atoi(argv[1]) : 10;
    vector<string> grid(size, string(size, '.'));
    int filled = fill(grid, 0, 0, '.', 1);
    cout << "size " << size << "x" << size << ": filled " << filled
         << ", deepest call " << deepest << "\n";
}

Build it with no optimisation, which is what plain g++ does by default, then run it with several sizes.

g++ -std=c++20 -Wall -O0 -o flood2 flood2.cpp
./flood2 10
./flood2 300
./flood2 360
./flood2 370
./flood2 1000

Here is the output on the machine used to write this lesson:

size 10x10: filled 100, deepest call 101
size 300x300: filled 90000, deepest call 90001
size 360x360: filled 129600, deepest call 129601
(no output, exit code 139)
(no output, exit code 139)

The 10 by 10 and 300 by 300 grids both work. The deepest call is one more than the number of cells. The extra call is the one that finds the edge of the grid, and it still counts as a level. The 360 by 360 grid works, with about 129,600 calls waiting at the deepest point. The 370 by 370 grid and the 1000 by 1000 grid both stop with exit code 139. On a Unix shell, exit code 139 means the program was killed with a segmentation fault. The program tried to use memory it does not own, and in this case that memory is the end of the call stack. The program printed nothing, because it crashed before the line that prints the result.

The machine's stack limit can be checked with ulimit -s. It printed 8192, which is in kilobytes, so the limit is 8 MB. Eight megabytes divided by the roughly 130,000 calls that fit gives about 60 to 65 bytes for each waiting call. The exact limit depends on the machine, the compiler and the compile flags, so the numbers here are only a guide. The shape of the result does not change. A recursive fill on a large open grid can need one call level per cell, and the stack has a fixed size.

Two ways to avoid this are common. You can change the recursion into a loop that keeps its own list of cells still to visit, stored in a vector. That is the explicit stack approach from the explicit stack lesson in this module. You can also use a breadth-first search, which spreads one ring of neighbours at a time with a queue. Both keep the depth small. Recursion is still the clearest way to write the fill for small grids, such as the ones in puzzles and in tests.

Common mistakes

Marking the cell after the calls. This is the most common bug in a flood fill. Here is a version where the mark comes last.

int fillLate(vector<string>& grid, int r, int c) {
    if (r < 0 || r >= (int)grid.size()) return 0;
    if (c < 0 || c >= (int)grid[r].size()) return 0;
    if (grid[r][c] != '.') return 0;
 
    int count = 1;
    count += fillLate(grid, r - 1, c);
    count += fillLate(grid, r + 1, c);
    count += fillLate(grid, r, c - 1);
    count += fillLate(grid, r, c + 1);
    grid[r][c] = '*';
    return count;
}

Run on a 3 by 3 grid of dots, this program prints nothing and exits with code 139. The cell at the top-left is still a dot while its neighbours are working. The neighbour below calls back to the cell above it, which is still a dot, and so the two cells call each other forever. The calls never end, the call stack runs out, and the program crashes. The fix is to move grid[r][c] = '*'; above the first recursive call.

Forgetting the bounds check. A row or column can be -1 or equal to the size of the grid when the fill steps off an edge. In C++, grid[r][c] does not check the index, so it reads memory outside the grid and the result is unpredictable. Using at() instead makes the program check the index and stop with a clear message. The next program asks for row 5 of a 3 row grid on purpose.

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
int main() {
    vector<string> grid = {"...", "...", "..."};
    cout << grid.at(5).at(0) << "\n";
}

The program prints this message and stops:

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 5) >= this->size() (which is 3)

The message says that index 5 was used on a vector with 3 elements. The exit code is 134, which means the program stopped itself after an error. The two bounds checks at the top of fill are there to stop the fill from ever making this call.

Removing the open check. If the line if (grid[r][c] != open) return 0; is deleted, the fill no longer stops at walls or at cells it has already marked. A marked cell calls its neighbours again, and they call it back, so the calls never end. On the 3 by 4 grid from the start of this lesson, the program exits with code 139 and prints nothing. The check at the top of the function is what makes the recursion stop.

Assuming a big grid is safe. The program in worked example 3 works on a 360 by 360 grid and crashes on a 370 by 370 grid. Nothing in the code changed between those two runs. Only the size changed. A test with a small grid will pass, and the same code will crash on a real map. When a fill can touch a lot of cells, use an explicit stack or a queue, or check the size before you run.

Practice

Exercise 1. Write a function regionSize that returns the size of the region containing a cell, without changing the grid. Use a second grid of bool values, called seen, to mark the cells already counted. Test it on the first grid in worked example 1, from the cell at row 0, column 0.

Show the answer

Each call first checks seen. A cell that is already seen returns 0. The cell is marked in seen, not in the grid, so the grid stays the same.

int regionSize(const vector<string>& grid, vector<vector<bool>>& seen, int r, int c, char open) {
    if (r < 0 || r >= (int)grid.size()) return 0;
    if (c < 0 || c >= (int)grid[r].size()) return 0;
    if (grid[r][c] != open || seen[r][c]) return 0;
 
    seen[r][c] = true;
    int count = 1;
    count += regionSize(grid, seen, r - 1, c, open);
    count += regionSize(grid, seen, r + 1, c, open);
    count += regionSize(grid, seen, r, c - 1, open);
    count += regionSize(grid, seen, r, c + 1, open);
    return count;
}

The program prints exercise 1 size: 20, and the first row of the grid still reads .....#...

Exercise 2. Count the islands in this grid using two rules. First, cells touch only through the four directions. Second, cells also touch diagonally. Which count is which?

#..
.#.
..#

Show the answer

With four directions, each # stands alone, so the count is 3. With eight directions, the three cells touch diagonally, so they form one island and the count is 1. The eight-direction version calls itself for all eight cells around it, and skips the centre cell.

void fill8(vector<string>& grid, int r, int c, char open) {
    if (r < 0 || r >= (int)grid.size()) return;
    if (c < 0 || c >= (int)grid[r].size()) return;
    if (grid[r][c] != open) return;
 
    grid[r][c] = '*';
    for (int dr = -1; dr <= 1; ++dr) {
        for (int dc = -1; dc <= 1; ++dc) {
            if (dr != 0 || dc != 0) fill8(grid, r + dr, c + dc, open);
        }
    }
}

The program prints exercise 2 four: 3 eight: 1.

Exercise 3. Find the bounding box of a region: the smallest top row, bottom row, left column and right column that contain every cell of the region. Pass the four numbers by reference, so that each call can update them.

Show the answer

Each filled cell updates the four values with min and max. Starting values are set high or low, so the first cell always replaces them.

void box(const vector<string>& grid, vector<vector<bool>>& seen, int r, int c, char open,
         int& top, int& bottom, int& left, int& right) {
    if (r < 0 || r >= (int)grid.size()) return;
    if (c < 0 || c >= (int)grid[r].size()) return;
    if (grid[r][c] != open || seen[r][c]) return;
 
    seen[r][c] = true;
    top = min(top, r);
    bottom = max(bottom, r);
    left = min(left, c);
    right = max(right, c);
    box(grid, seen, r - 1, c, open, top, bottom, left, right);
    box(grid, seen, r + 1, c, open, top, bottom, left, right);
    box(grid, seen, r, c - 1, open, top, bottom, left, right);
    box(grid, seen, r, c + 1, open, top, bottom, left, right);
}

For this grid, the region of # cells from row 1, column 1 covers rows 1 to 2 and columns 1 to 2. The program prints exercise 3 box: rows 1..2 cols 1..2.

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

Exercise 4. Without running the program, predict the value of "deepest call" when flood2 is given the size 50. Then run it to check.

Show the answer

The value is 2501. A 50 by 50 grid has 2500 cells, and the deepest call is one more than the cell count, as it was for the 10 by 10 and 300 by 300 grids. The run prints size 50x50: filled 2500, deepest call 2501.

Exercise 5. The grid in worked example 1 is passed by reference. Explain in plain words what would happen to the time and memory if it were passed by value, as vector<string> grid, and every call copied it.

Show the answer

Each call would make a full copy of the grid. The copy holds every row and every character, so a 50 by 50 grid would copy 2500 characters on every call. A fill that makes 2501 calls would copy about 6 million characters in total, with no change to the result. The copies also do not go away until each call returns, so the memory needed grows with the depth of the calls. A reference costs only the size of a pointer, which is the same whatever the grid size.

Summary

• A flood fill starts at one cell and visits its neighbours, using depth-first recursion.
• Each call checks the bounds and the cell type, marks the cell, then calls the four neighbours.
• Marking a cell before the neighbour calls is what stops the fill from looping forever.
• Counting islands is a loop over all cells that starts a fill at each unmarked piece of land.
• Each waiting call uses stack memory, so a fill on a large open grid can need one call level per cell and crash.
• An explicit stack or a queue keeps the depth small when the grid can be large.