Flood Fill

Grid with connected components colored by region

Flood fill is DFS or BFS starting from a single cell, spreading to all reachable cells of the same type. It's the algorithm behind the paint bucket tool in every image editor. More importantly, it's the building block for half the grid problems you'll ever solve. If you understand flood fill deeply, CSES Counting Rooms becomes a five-minute problem.

What Flood Fill Actually Does

Boundary check: validating in-bounds before visiting neighbors

Flood fill step by step: before and after filling a connected component

Start at cell \((r, c)\). Visit it. Then visit every unvisited neighbor that matches some condition (same color, same character, passable terrain). Repeat until you run out of reachable cells. That's it.

The result: you've marked every cell in one connected component. The "flood" spreads through all valid cells and stops at walls, grid boundaries, or already-visited cells.

void flood(int r, int c) {
    visited[r][c] = true;
    for (int d = 0; d < 4; d++) {
        int nr = r + dx[d], nc = c + dy[d];
        if (nr >= 0 && nr < H && nc >= 0 && nc < W
            && !visited[nr][nc] && grid[nr][nc] == '.') {
            flood(nr, nc);
        }
    }
}

Key insight. Flood fill is not a new algorithm. It is literally DFS (or BFS) applied to a grid. The only thing that varies between problems is the condition for spreading: same color, same character, elevation within a threshold, etc.

CSES Counting Rooms --- Full Walkthrough

Problem: Given an \(H \times W\) grid of . (floor) and # (wall), count the number of connected floor regions.

Approach: Loop over every cell. When you find an unvisited floor cell, flood fill from it and increment the count. Each flood fill marks one entire room.

#include <bits/stdc++.h>
using namespace std;

int H, W;
char grid[1005][1005];
bool visited[1005][1005];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void dfs(int r, int c) {
    visited[r][c] = true;
    for (int d = 0; d < 4; d++) {
        int nr = r + dx[d], nc = c + dy[d];
        if (nr >= 0 && nr < H && nc >= 0 && nc < W
            && !visited[nr][nc] && grid[nr][nc] == '.') {
            dfs(nr, nc);
        }
    }
}

int main() {
    cin >> H >> W;
    for (int i = 0; i < H; i++) cin >> grid[i];

    int rooms = 0;
    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++)
            if (grid[i][j] == '.' && !visited[i][j]) {
                dfs(i, j);
                rooms++;
            }

    cout << rooms << "\n";
}

Trace

Grid (5x8):

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

Step	Start Cell	Cells Visited	Rooms So Far
1	(1,1)	(1,1), (1,2)	1
2	(1,4)	(1,4), (1,5), (1,6), (2,4), (2,6), (3,4), (3,5), (3,6)	2
3	(3,1)	(3,1), (3,2)	3

Result: 3 rooms.

Component Labeling

Sometimes you don't just count components --- you need to know which component each cell belongs to. Assign an ID to each component during flood fill.

int label[1005][1005];
int compSize[1000005]; // size of each component

void dfs(int r, int c, int id) {
    label[r][c] = id;
    compSize[id]++;
    for (int d = 0; d < 4; d++) {
        int nr = r + dx[d], nc = c + dy[d];
        if (nr >= 0 && nr < H && nc >= 0 && nc < W
            && label[nr][nc] == 0 && grid[nr][nc] == '.') {
            dfs(nr, nc, id);
        }
    }
}

After labeling, label[r][c] tells you the component ID of cell \((r, c)\), and compSize[id] gives the area. This is useful when later queries ask "what component is cell X in?" or "how big is the island at position Y?"

Area Calculation

To find the area (number of cells) of a component, just count cells during flood fill.

int dfs(int r, int c) {
    visited[r][c] = true;
    int area = 1;
    for (int d = 0; d < 4; d++) {
        int nr = r + dx[d], nc = c + dy[d];
        if (nr >= 0 && nr < H && nc >= 0 && nc < W
            && !visited[nr][nc] && grid[nr][nc] == '.') {
            area += dfs(nr, nc);
        }
    }
    return area;
}

Call dfs(r, c) and it returns the size of the component containing \((r, c)\). To find the largest component, track the maximum across all DFS calls.

Perimeter Calculation

The perimeter of a component is the number of edges between the component and "not the component" (walls or grid boundary).

For each cell in the component, check all four neighbors. If a neighbor is out of bounds or is a wall, that's one perimeter edge.

int perimeter(int sr, int sc) {
    queue<pair<int,int>> q;
    q.push({sr, sc});
    visited[sr][sc] = true;
    int perim = 0;
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nr = r + dx[d], nc = c + dy[d];
            if (nr < 0 || nr >= H || nc < 0 || nc >= W
                || grid[nr][nc] == '#') {
                perim++; // boundary edge
            } else if (!visited[nr][nc]) {
                visited[nr][nc] = true;
                q.push({nr, nc});
            }
        }
    }
    return perim;
}

Perimeter Trace

Island in a 4x4 grid:

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

The island has 4 cells. Each cell contributes edges toward walls:

Cell	Right	Left	Down	Up	Perimeter Contribution
(1,1)	`.` neighbor	`#` wall	`.` neighbor	`#` wall	2
(1,2)	`#` wall	`.` neighbor	`.` neighbor	`#` wall	2
(2,1)	`.` neighbor	`#` wall	`#` wall	`.` neighbor	2
(2,2)	`#` wall	`.` neighbor	`#` wall	`.` neighbor	2

Total perimeter: 8.

Key insight. Perimeter = (4 x area) minus (2 x number of internal edges). Each internal edge reduces the perimeter by 2 (one from each adjacent cell). For the 2x2 island: \(4 \times 4 - 2 \times 4 = 8\).

Recursive DFS vs Iterative DFS

Recursive DFS is clean but has a fatal flaw: stack overflow. Each recursive call adds a frame to the call stack. A grid of size \(1000 \times 1000\) has up to \(10^6\) cells in one component. Most systems default to a stack size of 1--8 MB, which supports roughly \(10^4\) to \(10^5\) recursive calls.

Symptoms: your solution works on small inputs, crashes with a segfault or "stack overflow" on large ones. No wrong-answer verdict --- just a runtime error.

Fix: use an explicit stack (iterative DFS) or switch to BFS.

int dfs_iterative(int sr, int sc) {
    stack<pair<int,int>> st;
    st.push({sr, sc});
    visited[sr][sc] = true;
    int area = 0;
    while (!st.empty()) {
        auto [r, c] = st.top(); st.pop();
        area++;
        for (int d = 0; d < 4; d++) {
            int nr = r + dx[d], nc = c + dy[d];
            if (nr >= 0 && nr < H && nc >= 0 && nc < W
                && !visited[nr][nc] && grid[nr][nc] == '.') {
                visited[nr][nc] = true;
                st.push({nr, nc});
            }
        }
    }
    return area;
}

Gotcha. On CSES and Codeforces, you can increase the stack size with a compile flag (-Wl,--stack,67108864 on Windows or ulimit -s unlimited on Linux). But this is a band-aid. Iterative DFS or BFS is the robust solution.

BFS Flood Fill

BFS explores cells in order of distance from the start. For pure flood fill (where you just need to visit all reachable cells), BFS and DFS give the same result. But BFS has two advantages:

No stack overflow risk --- it uses a queue on the heap.
Gives shortest distances for free --- useful in later lessons.

int bfs(int sr, int sc) {
    queue<pair<int,int>> q;
    q.push({sr, sc});
    visited[sr][sc] = true;
    int area = 0;
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        area++;
        for (int d = 0; d < 4; d++) {
            int nr = r + dx[d], nc = c + dy[d];
            if (nr >= 0 && nr < H && nc >= 0 && nc < W
                && !visited[nr][nc] && grid[nr][nc] == '.') {
                visited[nr][nc] = true;
                q.push({nr, nc});
            }
        }
    }
    return area;
}

Gotcha. When flood fill is all you need (no shortest path, no distance), pick BFS by default on grids. It's equally fast and won't crash on a \(1000 \times 1000\) grid.

When to Use What

Situation	Use
Count components	DFS or BFS (either works)
Find largest component	DFS or BFS + area tracking
Need shortest distance	BFS only
Grid is \(\leq 500 \times 500\)	Recursive DFS is fine
Grid is \(> 500 \times 500\)	BFS or iterative DFS
Need to label components	DFS or BFS + label array

Exercises

Count and size. For CSES Counting Rooms, modify the solution to also print the size of the largest room and the size of the smallest room.
Perimeter challenge. Given an island grid (1 = land, 0 = water), compute the total perimeter of all islands combined. Can you do it without flood fill? (Hint: for each land cell, count how many of its 4 neighbors are water or out-of-bounds.)
Component merging. Given a grid, for each wall cell, compute what the area of the largest component would be if that wall cell became floor. Can you solve this in \(O(H \times W)\) total, not per query? (Hint: label components first, then for each wall cell, look at its neighbors' component IDs.)
Stack overflow test. Create a \(1000 \times 1000\) grid that is entirely floor. Run recursive DFS on it. Does it crash? Now try iterative DFS or BFS. Compare.

Problems

Problem	Link	Difficulty
CSES Counting Rooms	cses.fi/problemset/task/1192	Easy
LC 695 --- Max Area of Island	leetcode.com/problems/max-area-of-island	Medium
LC 463 --- Island Perimeter	leetcode.com/problems/island-perimeter	Easy
LC 827 --- Making a Large Island	leetcode.com/problems/making-a-large-island	Hard