Count Islands
Hard · rating 1750 · Graphs
The first line contains r and c. The next r lines each contain a string of c characters that are 0 (water) or 1 (land). Print the number of islands — maximal groups of 1s connected horizontally or vertically.
Constraints: 1 ≤ r, c ≤ 1000
Editorial
Approach
Scan the grid. Every time you hit an unvisited 1, you've found a new island — increment the count, then flood-fill (DFS or BFS) all connected land, marking it visited so it isn't counted again.
Flood fill
From the starting cell, repeatedly visit the four orthogonal neighbours that are still land, sinking each to 0 as you go. When the fill finishes, the whole island is consumed.
for each cell (i, j):
if grid[i][j] == '1':
count += 1
stack = [(i, j)]; grid[i][j] = '0'
while stack:
y, x = stack.pop()
for ny, nx in neighbours(y, x):
if grid[ny][nx] == '1':
grid[ny][nx] = '0'; stack.append((ny, nx))Complexity
Time: O(r·c) — each cell is visited once. Space: O(r·c) worst case for the stack.