Grid flood fill and island counting

Why this matters

A grid is a table of squares, like a chess board or the pixels of a small image. Many everyday programs work on grids. The paint bucket in an image editor fills a region of same-coloured pixels. A game checks whether a character can walk from one tile to another. A map program counts the separate patches of land in a satellite image. All of these questions have the same shape. You start at one cell, look at the cells next to it, and keep going while a rule allows it.

That shape is a graph search. The earlier lesson on breadth-first search (BFS) and depth-first search (DFS) worked on graphs given as lists of links. A grid does not come with a list of links, but it does not need one. Each cell is a node, and the cells touching it are its neighbours. You can find the neighbours with a little arithmetic, so the two searches work on a grid with only small changes.

This lesson uses that idea for two jobs. The first is counting islands, which means counting separate groups of land in a map. The second is flood fill, which means changing the colour of one whole region at once.

A grid is a graph

Here is a small grid. The character 1 marks land and 0 marks water.

11000
11000
00100
00011

Two land cells are connected when they share a side. Cells that touch only at a corner do not count as connected in this lesson. A group of connected land cells is one island. This grid has three islands: a block of four cells in the top left, a single cell in the middle, and a pair of cells in the bottom right.

Two words from graph theory are useful here. A node is one thing in the graph. In a grid, each cell is a node. An edge is a link between two nodes. In a grid, an edge joins two land cells that share a side. The neighbours of a cell are the cells it has an edge to. Each cell has up to four neighbours: the cell above, below, to the left and to the right. A cell on the border has fewer, because some of those four positions are outside the grid.

The four moves can be stored in two small arrays. Each move changes the row by one amount and the column by another amount.

constexpr int dr4[] = {-1, 1, 0, 0};
constexpr int dc4[] = {0, 0, -1, 1};

Move number k goes from the cell at row r and column c to the cell at row r + dr4[k] and column c + dc4[k]. Move 0 goes up, move 1 goes down, move 2 goes left and move 3 goes right. A loop from 0 to 3 visits all four neighbours. The arrays also make it easy to add or remove moves later.

Before a search looks at a cell, it must check that the cell is inside the grid. Stepping up from row 0 gives row -1, which does not exist. The helper below does that check.

using Grid = std::vector<std::string>;
 
int rowsOf(const Grid& g) { return static_cast<int>(g.size()); }
int colsOf(const Grid& g) { return static_cast<int>(g[0].size()); }
 
bool inside(const Grid& g, int r, int c) {
    return r >= 0 && r < rowsOf(g) && c >= 0 && c < colsOf(g);
}

The && operator checks its left side first and stops as soon as the answer is known. So r >= 0 is checked before g[r] is ever used. The order of the checks matters, and a later section shows what goes wrong when it is reversed.

The two helpers rowsOf and colsOf convert the size() result to int. The size() function returns an unsigned number, and mixing it with int in a comparison causes a warning. The static_cast<int> turns the number into a normal signed integer first.

Counting islands with DFS

The counting plan has two parts. Scan every cell from top to bottom and left to right. When you meet land, you have found a new island, because every cell of any earlier island has already been removed. Add one to the count. Then remove the whole island, by turning its land cells into water. Removing them means the scan will never count the same island twice. This turns the grid itself into the record of what was visited, so no separate visited array is needed.

The removal is a depth-first search. From a land cell, it goes to a land neighbour, then to a land neighbour of that one, and so on until no land is left next to it. Then it backs up and tries the other neighbours. Each call handles one cell.

void sinkDfs(Grid& g, int r, int c) {
    if (!inside(g, r, c) || g[r][c] != '1') return;
    g[r][c] = '0';
    for (int k = 0; k < 4; ++k) sinkDfs(g, r + dr4[k], c + dc4[k]);
}
 
int countIslandsDfs(Grid g) {
    int count = 0;
    for (int r = 0; r < rowsOf(g); ++r)
        for (int c = 0; c < colsOf(g); ++c)
            if (g[r][c] == '1') {
                ++count;
                sinkDfs(g, r, c);
            }
    return count;
}

The function takes Grid g by value in countIslandsDfs, so the caller's grid is not changed. The sinkDfs function takes Grid& g by reference, because it has to change the cells.

Let us trace the search on the three-island grid from the start of the lesson. The scan reaches cell (0, 0), which is row 0 and column 0, and finds land. The count becomes 1. The call sinkDfs(g, 0, 0) turns (0, 0) into 0. Its first move is up, which is outside the grid, so that call returns at once. Its second move is down to (1, 0), which is land. That call turns (1, 0) into 0. From (1, 0) the moves are up to (0, 0), now water, so it returns; down to (2, 0), which is water; left, which is outside; and right to (1, 1), which is land. The call at (1, 1) turns it into water and tries its neighbours. Up is (0, 1), which is land, so that call turns it into water too. From (0, 1), every neighbour is water or outside. The search then backs up to (1, 1), tries its remaining neighbours, and backs up again. When every call has returned, the four cells of the top-left island are water.

The scan carries on. It meets no more land until (2, 2), which is the single middle cell. The count becomes 2 and that island is sunk. The scan then reaches (3, 3), the first cell of the bottom-right pair. The count becomes 3, and the search sinks (3, 3) and (3, 4). No land is left, so the answer is 3.

Here is the output of this program on the same grid.

islands (DFS): 3

The rule to remember is this. Each island is counted once, at the first of its cells that the scan reaches. The depth-first search then removes the rest of that island, so the scan never reaches it again.

Counting islands with BFS

The same count can be made with a breadth-first search. BFS uses a queue instead of recursion. The queue holds cells that have been found but not yet checked. You take the front cell, look at its neighbours, add any new land neighbours to the back of the queue, and repeat until the queue is empty.

The important detail is when a cell is removed from the grid. In this version, a cell is turned into water as soon as it is put in the queue. If you waited until it was taken out of the queue, two neighbours could both add the same cell before either one was processed. The cell would then sit in the queue twice. The final count would still be right, but the search would do extra work for every duplicate.

using Cell = std::pair<int, int>;
 
int countIslandsBfs(Grid g) {
    int count = 0;
    for (int r = 0; r < rowsOf(g); ++r)
        for (int c = 0; c < colsOf(g); ++c) {
            if (g[r][c] != '1') continue;
            ++count;
            std::queue<Cell> q;
            g[r][c] = '0';
            q.push({r, c});
            while (!q.empty()) {
                auto [cr, cc] = q.front();
                q.pop();
                for (int k = 0; k < 4; ++k) {
                    int nr = cr + dr4[k], nc = cc + dc4[k];
                    if (inside(g, nr, nc) && g[nr][nc] == '1') {
                        g[nr][nc] = '0';
                        q.push({nr, nc});
                    }
                }
            }
        }
    return count;
}

The code uses auto [cr, cc] = q.front();, which is a structured binding. It unpacks the pair into two named values. This needs C++17 or later. The course compiles with -std=c++20.

The output on the same grid is the same.

islands (BFS): 3

DFS and BFS find the same islands. They differ in the order of visiting and in how they store the cells they are still working on. DFS stores them on the call stack, which is the list of calls that are still running. BFS stores them in a queue on the heap, which is memory the program asks for while it runs. This difference matters for very large grids, and a later section covers it.

Flood fill: painting one region

A flood fill starts at one cell and changes the colour of every cell connected to it that has the same colour. An image editor's paint bucket does exactly this. The rule is the same as before: a neighbour is part of the region only when it touches the region along a side and has the same colour as the start.

Take this grid of three colours.

AAB
ABB
AAA

A flood fill from row 0, column 0 with the colour X should change the A cells that are connected to the top-left corner. Those are six cells: the top two, the one in the middle left, and the bottom three. The B cells stay the same.

void floodFill(Grid& g, int sr, int sc, char newColor) {
    char oldColor = g[sr][sc];
    if (oldColor == newColor) return;
    std::queue<Cell> q;
    g[sr][sc] = newColor;
    q.push({sr, sc});
    while (!q.empty()) {
        auto [cr, cc] = q.front();
        q.pop();
        for (int k = 0; k < 4; ++k) {
            int nr = cr + dr4[k], nc = cc + dc4[k];
            if (inside(g, nr, nc) && g[nr][nc] == oldColor) {
                g[nr][nc] = newColor;
                q.push({nr, nc});
            }
        }
    }
}

The first line remembers the colour that was there before. The check oldColor == newColor stops the function early when there is nothing to change. Without that check the function would never end. A neighbour is repainted with the new colour, which is also the old colour, so it still matches oldColor. It would be added to the queue again and again, forever.

The function is called like this.

Grid paint = {
    "AAB",
    "ABB",
    "AAA",
};
floodFill(paint, 0, 0, 'X');

Here is the resulting grid, printed row by row.

after flood fill from (0,0) with X:
XXB
XBB
XXX

The six A cells became X. The three B cells stay the same. The B in the middle row touches the X region, but its colour is different from A, so the fill does not enter it. Flood fill follows one colour at a time.

Island size: a harder example

The next example asks for more than a count. It asks for the size of the largest island. The change is small. The depth-first search now returns how many cells it sank, instead of returning nothing.

int areaDfs(Grid& g, int r, int c) {
    if (!inside(g, r, c) || g[r][c] != '1') return 0;
    g[r][c] = '0';
    int area = 1;
    for (int k = 0; k < 4; ++k) area += areaDfs(g, r + dr4[k], c + dc4[k]);
    return area;
}
 
int largestIsland(Grid g) {
    int best = 0;
    for (int r = 0; r < rowsOf(g); ++r)
        for (int c = 0; c < colsOf(g); ++c)
            if (g[r][c] == '1') best = std::max(best, areaDfs(g, r, c));
    return best;
}

Each call to areaDfs counts its own cell, which is the 1, and then adds the counts that its neighbour calls return. A cell with no land around it returns 1. A call on a water cell or outside the grid returns 0, so it adds nothing. The total for an island is the number of land cells in it.

Check the answer on the three-island grid. The islands have 4, 1 and 2 cells. The largest is 4. The total number of land cells is 4 + 1 + 2 = 7, which matches a count of the 1 characters in the grid, so the sizes add up.

largest island: 4

std::max comes from the <algorithm> header. Forgetting that header is one of the common mistakes below.

A useful habit is to check that the parts add up to a whole. Here the island sizes must sum to the number of land cells. If the sum is off, the search is either missing cells or counting one cell twice.

Diagonal moves change the answer

The rule that two cells are connected only along a side is a choice. Some puzzles count diagonal touching as connected too. This is called 8-way connection, because each cell then has eight neighbours instead of four. The only change to the code is the list of moves, which now includes the four diagonals.

The count changes too. Here is a grid with two cells on a diagonal.

10
01

With four-way moves, the two land cells are not connected, so there are two islands. With eight-way moves, the top-left cell and the bottom-right cell touch at a corner, so they form one island. Inside the BFS above, replace the four-way loop with this one.

for (int dr = -1; dr <= 1; ++dr)
    for (int dc = -1; dc <= 1; ++dc) {
        int nr = cr + dr, nc = cc + dc;
        if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
        if (g[nr][nc] == '1') {
            g[nr][nc] = '0';
            q.push({nr, nc});
        }
    }

This loop also visits the cell itself, where dr and dc are both zero. That cell is already water when the loop looks at it, so the loop skips it. This is why no special case is needed.

The result on the diagonal pair is shown below. The first line is the four-way count from the main program. The second line is the eight-way count from a separate run.

diagonal pair, 4-way islands: 2
8-way islands in b: 1

Always read the problem for the connection rule before you write any code. Changing the moves is easy. Choosing the right one is the real decision.

Recursion depth on large grids

The depth-first version uses one function call for each cell it visits, and it keeps every call on the call stack until that call finishes. The call stack has a fixed size, set by the operating system. On a Linux machine it is often 8 MB. A search over a big island can go deep enough to use it all.

The test below runs sinkDfs on a square grid where every cell is land. The size is given on the command line.

$ ulimit -s
8192
$ ./deep 400
sunk 400 x 400 grid
$ ./deep 450
$ echo $?
139

The grid of 400 by 400 cells finished, and the program printed its message. The grid of 450 by 450 cells did not print. The exit code is 139, which means the program was killed by a segmentation fault, a crash caused by using memory the program is not allowed to use. The exit code is 128 plus the signal number 11, which is the signal for that kind of crash. The exact limit depends on the machine, the compiler and the optimisation level. The runs above used -O0, which means no optimisation, and g++ 15.2.0 on Ubuntu.

The BFS version does not have this problem in the same way. Its queue lives on the heap, which is the memory area that grows as the program asks for more. The queue still holds many cells at once, but it is limited by the memory of the machine, not by the call stack. For a grid that can be large, use BFS, or write the depth-first search with an explicit stack of cells that you manage yourself.

Common mistakes

The examples below use real messages from g++ 15.2.0 on Ubuntu, compiled with -std=c++20 -Wall.

Checking the cell before the bounds

The first mistake is reading a cell before checking that its row and column are in the grid. This function is wrong.

int badCount(const Grid& g, int r, int c) {
    if (g[r][c] == '1' && r >= 0 && c >= 0) return 1;
    return 0;
}

When it is called as badCount(g, -1, 0), the program reads g[-1], which is outside the grid. The standard library on this system checks that kind of access and stops the program. The start of the message it printed is shown below. The middle of the line is the function signature, which is cut here.

/usr/include/c++/15/bits/stl_vector.h:1282: constexpr std::vector<_Tp, _Alloc>::const_reference std::vector<_Tp, _Alloc>::operator[](size_type) const [with ...]: Assertion '__n < this->size()' failed.

The program then stopped with exit code 134. On another system the same bug can show up as a crash or as a wrong value, so the check must come first. The fixed order is this.

if (r >= 0 && r < rowsOf(g) && c >= 0 && c < colsOf(g) && g[r][c] == '1') return 1;

The && operator stops at the first false part, so the cell is read only after its row and column are known to be valid.

Comparing int with size()

The second mistake is a loop that compares a signed int with the unsigned result of size().

for (int r = 0; r < g.size(); ++r) total += static_cast<int>(g[r].size());

The compiler gives this warning with -Wall.

mistakes.cpp:7:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::__cxx11::basic_string<char> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]

The warning is about a real risk. An int that goes negative compares as a very large unsigned number, so a loop can behave in a way you did not expect. The fix is to use the rowsOf and colsOf helpers from earlier, which return int.

Forgetting an include

The third mistake is using a type without including its header. This program uses std::queue but does not include <queue>.

#include <iostream>
#include <utility>
#include <vector>
 
int main() {
    std::queue<std::pair<int, int>> q;
    q.push({0, 0});
    auto [r, c] = q.front();
    std::cout << r << c << '\n';
    return 0;
}

The compiler reports this error first. The file line numbers refer to this exact file.

nocompile.cpp:6:10: error: ‘queue’ is not a member of ‘std’
    6 |     std::queue<std::pair<int, int>> q;
      |          ^~~~~
nocompile.cpp:4:1: note: ‘std::queue’ is defined in header ‘<queue>’; this is probably fixable by adding ‘#include <queue>’

The fix is to add #include <queue>. The later errors in the same output, such as q not being declared, are a result of the first one, so read the first error and fix that before the rest.

Marking cells when they are popped

Some students mark a cell as water only when it is taken off the queue. Both the answer and the output of the program can stay correct in this case, because a duplicate cell is simply skipped when it is found again. The problem is the extra work. A cell can be added to the queue by up to four neighbours before the first copy is removed, so the queue grows larger than it needs to be. Mark a cell when you add it, as the BFS code above does.

Flood fill with the same colour

If newColor equals the colour already there, the flood fill from earlier never stops. There is no error message. The program simply keeps running and must be stopped by hand. The guard at the top of floodFill prevents this, and it is the first thing to check when a fill seems to hang.

Using the wrong bit for a letter

The door example in the next lesson uses one bit per letter. A common slip is to compute the bit for a capital letter from the lowercase letter 'a'. Here is that mistake, run with the undefined-behaviour checker turned on.

shift.cpp:7:17: runtime error: shift exponent -32 is negative

The letter 'A' has the code 65 and 'a' has the code 97, so 'A' - 'a' is -32. Shifting by a negative amount is undefined. The lesson on state-space search shows the correct form.

Practice

Each exercise is followed by its answer. Try each one on paper or in a small program before you read the answer.

Exercise 1

Count the islands in this grid, using four-way moves.

1101
1101
0000
1001

Show the answer

There are four islands. The top-left block has four land cells. The two cells in the right-hand column of the top two rows form a pair. The cell in the bottom left is on its own, and the cell in the bottom right is on its own. The count is 4. A program that counts the islands in this grid prints 4-way islands in a: 4.

Exercise 2

The grid below has two land cells touching at a corner. How many islands are there with four-way moves, and how many with eight-way moves?

10
01

Show the answer

With four-way moves there are 2 islands, because the two cells do not share a side. With eight-way moves there is 1 island, because the diagonal counts as a touch. The program prints 8-way islands in b: 1 for the second case.

Exercise 3

Use the paint grid from the flood fill section. How many cells change if you flood fill from row 2, column 0 with the colour Y?

AAB
ABB
AAA

Show the answer

Six cells change. The cell at row 2, column 0 is A, and every A cell is connected to it. Those are the same six A cells that changed in the earlier example, so the answer is 6. The two B cells stay as they are.

Exercise 4

Why does sinkDfs not need a separate array to remember which cells it has visited?

Show the answer

Each sunk cell is changed to water. The search only moves into cells that are still land, so it never enters a cell it has already sunk. The grid itself records what has been visited. The cost is that the grid is changed, so the caller must pass a copy when the original is still needed.

Exercise 5

Write a function that returns the number of land cells in the grid. Then explain why the sum of the island sizes from largestIsland cannot be larger than that number.

Show the answer

The function is a single loop that counts every cell equal to '1'.

int countLand(const Grid& g) {
    int total = 0;
    for (const auto& row : g)
        for (char ch : row)
            if (ch == '1') ++total;
    return total;
}

Every island is a set of different land cells, and no cell belongs to two islands. So the island sizes add up to exactly the number of land cells, and no sum can be larger.

Summary

• A grid is a graph: each cell is a node, and cells that share a side are neighbours.
• The four moves are stored as two small arrays, and every move is checked against the grid's bounds before the cell is read.
• To count islands, scan the grid, count each new piece of land once, and remove the whole island with a search.
• A flood fill changes one region of one colour. Guard against the case where the new colour equals the old one.
• Depth-first search uses the call stack and can crash on very large grids. Breadth-first search uses a queue and is safer for big inputs.