Number of islands: flood fill and border regions

Number of islands asks how many separate groups of land a grid holds, where two land cells belong together when a chain of land cells sharing sides joins them. Each island is a connected component of the grid’s graph, so the count is the number of searches it takes to mark all the land: one flood fill from every land cell that no earlier search reached. Grids show up in coding rounds as maps, boards, images and seating plans, and the same fill also answers which regions can reach the border.

The problem: islands on a survey map

Three examples:

1. The 5 × 8 survey map in the diagram has 5 islands. Islands C and E touch only at a corner, so they stay apart.
2. A map of water only, such as three rows of ...., has 0 islands.
3. The single row #.#.## has 3 islands: two single cells and a pair.

The brute force: relabel until nothing changes

A method that needs no graph idea: give every land cell its own label, then sweep the map again and again, letting each land cell take the smallest label among itself and its land neighbours. When a sweep changes nothing, each island holds one label, so the answer is the number of distinct labels. It is correct, and on the survey map it takes 3 sweeps. The run then tries winding islands, full rows joined at alternate ends:

"""Islands by relabelling: every land cell takes the smallest label among itself and its land neighbours, sweep after
sweep, until a sweep changes nothing. Correct, but a winding island needs a sweep for almost every cell it has."""

SURVEY = [
    "##..#...",
    "#...##..",
    "..#..#.#",
    ".###...#",
    "....#.##",
]


def islands_by_relabelling(grid):
    rows, cols = len(grid), len(grid[0])
    label = [[r * cols + c if grid[r][c] == "#" else -1 for c in range(cols)] for r in range(rows)]
    sweeps = 0
    changed = True
    while changed:
        changed = False
        sweeps += 1
        for r in range(rows):
            for c in range(cols):
                if label[r][c] < 0:
                    continue
                best = label[r][c]
                for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and 0 <= label[nr][nc] < best:
                        best = label[nr][nc]
                if best < label[r][c]:
                    label[r][c] = best
                    changed = True
    count = len({x for row in label for x in row if x >= 0})
    return count, sweeps


def snake(k):
    """A k x k map holding one island that winds back and forth: full rows joined at alternate ends."""
    grid = []
    for r in range(k):
        if r % 2 == 0:
            grid.append("#" * k)
        elif r % 4 == 1:
            grid.append("." * (k - 1) + "#")
        else:
            grid.append("#" + "." * (k - 1))
    return grid


count, sweeps = islands_by_relabelling(SURVEY)
print(f"Survey map, 5 x 8: {count} islands after {sweeps} sweeps")
print()
print("Winding islands:")
print("    k  land cells  sweeps  cells read")
for k in (8, 16, 32, 64):
    g = snake(k)
    count, sweeps = islands_by_relabelling(g)
    land = sum(row.count("#") for row in g)
    print(f"{k:>5} {land:>11,} {sweeps:>7,} {sweeps * k * k:>11,}   islands: {count}")

Survey map, 5 x 8: 5 islands after 3 sweeps

Winding islands:
    k  land cells  sweeps  cells read
    8          36      16       1,024   islands: 1
   16         136      62      15,872   islands: 1
   32         528     250     256,000   islands: 1
   64       2,080   1,010   4,136,960   islands: 1

The labels flow with the sweep along some rows and against it along others, one cell per sweep. So a winding island needs about k²/4 sweeps on a k × k map: 1,010 at k = 64, which read 4,136,960 cells. At 1,000 × 1,000 that is about 250,000 sweeps of a million cells, 2.5 × 10¹¹ cell visits of four neighbour checks each: hours, even in C++.

What to notice

An island is a set of cells that a single search reaches from any one of its cells. So start a flood fill from the first unmarked land cell, mark everything it reaches, add 1 to the count, and continue the scan. Each cell is marked once and looked at from its four neighbours, so the whole count is O(rows × cols), about 5 million steps at the limits. Border regions follow the same idea in reverse: one search started from every border cell at once marks everything that can reach the edge.

Flood fill: one search per island Pro: opens with a Pro, Premium or Ultimate pass