Grid graphs & flood fill

Overview

A grid is secretly a graph: every cell is a vertex linked to its four orthogonal neighbours. Flood fill is just DFS/BFS on that hidden graph — starting from a cell, it spreads to all connected cells of the same kind. It powers island counting, the paint-bucket tool, and connected-region labelling.

Why it matters

Grid/flood-fill problems are ubiquitous: image segmentation and the paint bucket, counting regions in maps or game boards, maze and terrain analysis, and connected-component labelling in computer vision.

Core concepts

Implicit adjacency. Cell (r,c) neighbours (r±1,c) and (r,c±1) — no matrix needed.

Marking. Sink each filled cell (set it to 0) or use a separate visited grid so you never revisit.

Counting vs sizing. Each flood you start is one island; the number of cells a flood consumes is that island's size.

4- vs 8-connectivity. These problems use 4-directional adjacency; diagonals would merge more regions.

Syntax notes

/* recursive 4-connected flood fill; sinks each filled cell so it is not revisited */
static int fill(int *g, int rows, int cols, int i, int j) {
    if (i < 0 || i >= rows || j < 0 || j >= cols) return 0;   /* BOUNDS FIRST */
    if (g[i*cols + j] != 1) return 0;                          /* not land, or already filled */
    g[i*cols + j] = 0;                                         /* sink it - no visited array needed */
    return 1 + fill(g,rows,cols,i+1,j) + fill(g,rows,cols,i-1,j)
             + fill(g,rows,cols,i,j+1) + fill(g,rows,cols,i,j-1);
}

int count_islands(const int *grid, int rows, int cols) {
    int *g = malloc((size_t)rows * cols * sizeof *g);          /* work on a COPY */
    if (!g) return -1;
    for (int k = 0; k < rows*cols; k++) g[k] = grid[k];
    int islands = 0;
    for (int i = 0; i < rows; i++)
        for (int j = 0; j < cols; j++)
            if (g[i*cols + j] == 1) { fill(g,rows,cols,i,j); islands++; }
    free(g);
    return islands;
}

Key points:

• Bounds are checked before the array read; || short-circuits left to right, so this ordering is what keeps it safe.
• Sinking the cell to 0 doubles as the visited marker — no separate array needed.
• The copy protects the caller's grid; const on the parameter documents that guarantee.

Lesson

A grid is a graph in disguise: each cell is a vertex joined to its four orthogonal neighbours. Flood fill is DFS/BFS on that implicit graph — it powers count the islands and size the largest island of connected 1-cells, the paint-bucket tool, and region labelling. Work on a copy (or mark cells) so you never revisit, and never connect diagonally unless asked.

Code examples

#include <stdio.h> static int R=4,Cc=5; static int g[20]={ 1,1,0,0,1, 1,0,0,1,1, 0,0,1,0,0, 1,0,1,1,0 }; static int fill(int i,int j){ if(i<0||i>=R||j<0||j>=Cc||g[iCc+j]!=1) return 0; g[iCc+j]=0; return 1+fill(i+1,j)+fill(i-1,j)+fill(i,j+1)+fill(i,j-1); } int main(void){ int islands=0, biggest=0; for(int i=0;i<R;i++) for(int j=0;j<Cc;j++) if(g[i*Cc+j]==1){ int s=fill(i,j); islands++; if(s>biggest)biggest=s; } printf("islands=%d largest=%d\n", islands, biggest); return 0; }

Line by line

Common mistakes

Connecting cells diagonally when only orthogonal moves are allowed. Mutating the caller's grid instead of a copy. Bounds errors at the grid edges. Forgetting to track the running maximum when sizing.

Debugging tips

Compiler errors and warnings:

• warning: passing 'const int *' to parameter of type 'int *' — a useful signal that fill mutates and therefore needs the copy.
• No warning for checking bounds after the read.

Runtime symptoms:

• Segfault or sanitizer report. The bounds check runs after g[i*cols + j], or is missing a side (a j < 0 omission is easy to miss).
• Every land cell counts as its own island. You never sank the cell, so the outer scan keeps finding it.
• Islands merge that should not. You added diagonal neighbours; 4-connectivity is 4 calls, not 8.
• The caller's grid is destroyed. You filled in place instead of on a copy.
• Wrong on a non-square grid. The stride must be cols; using rows works only when the grid is square, which is why square test data hides this bug.
• Stack overflow on a large uniform grid. Depth can reach rows*cols; use an explicit stack or BFS.

Technique: test a 1xN strip, an all-land grid, an all-water grid, and a non-square grid. The non-square case catches stride bugs that square tests cannot.

Memory safety

• Bounds before dereference — the central rule. i < 0 || i >= rows || j < 0 || j >= cols must be fully evaluated before g[i*cols + j]. Relying on the read to "fail" is undefined behaviour, and a negative index reads before the allocation.
• Stride correctness. For a rows x cols grid the index is i*cols + j. A wrong stride stays inside the allocation, so nothing crashes — the answer is simply wrong. Square test grids hide this; always test rectangular.
• Mutation and ownership. fill writes to the grid, so either copy the input (as here) or document that the caller's data is consumed. Taking const on the public function and copying internally is the safer contract.
• Allocation size rows * cols can overflow int; compute in size_t and validate both dimensions are positive.
• Recursion depth can reach the number of cells — a 1000x1000 solid grid is a million frames. Iterative flood fill (explicit stack or BFS queue) removes that risk.

Real-world uses

Concrete uses: The paint-bucket tool in every image editor, connected-component labelling in computer vision, counting distinct regions in satellite or medical imagery, terrain and territory analysis in games, and mine-sweeper-style reveal cascades. The same implicit-graph idea drives maze solving and reachability on tile maps.

Professional best practices:

Beginner:

• Write the bounds guard first, as one complete condition.
• Decide explicitly between 4- and 8-connectivity; they give different answers.

Intermediate:

• Use an explicit stack or BFS queue for large grids to avoid stack exhaustion.
• Prefer a separate visited array when the input grid must be preserved and copying is expensive.
• Label each region with an id rather than just counting when downstream code needs to work per region.

Practice tasks

1. (Beginner) Count islands. Implement int count_islands(const int *grid, int rows, int cols) on a copy. Example: the demo grid -> 4. Concepts: flood fill, sinking cells.

2. (Beginner) Largest island. Implement int max_island_size(...) using the fill's return value. Example: -> 3. Concepts: sizing a region.

3. (Intermediate) Rectangular grids. Test a 2x5 and a 5x2 grid to prove your stride is cols, not rows. Concepts: stride bugs square tests hide.

4. (Intermediate) Iterative fill. Rewrite with an explicit stack so a 1000x1000 solid grid cannot exhaust the call stack. Concepts: removing recursion depth limits.

Summary

A grid is a graph in disguise: each cell is a vertex joined to its four orthogonal neighbours, and flood fill is simply DFS on that implicit graph. Sinking each filled cell to 0 serves as the visited marker, so the number of fills the outer scan starts is the island count and each fill's return value is that island's size. Two rules dominate correctness: check all four bounds before reading the cell (a negative index is an out-of-bounds read, not a harmless miss), and use cols as the row stride — a wrong stride stays inside the allocation and silently corrupts the answer, which square test grids will never reveal. Work on a copy to protect the caller's data, and switch to an iterative fill for large grids since depth can reach the cell count.

Practice with these exercises

• Count islands (flood fill)
• Largest island size