Island
This is the classic connected-components-on-a-grid problem, solved by flood fill. Algorithm Iterate through every cell (i, j) in the grid. When an unvisited land cell is found, increment the island counter and perform...
Problem Statement
Rendered from the "Problem Statement" section in the LaTeX write-up.
Given an $R \times C$ grid where each cell is either land (1) or water (0), count the number of islands. An island is a maximal connected component of land cells under 4-directional adjacency (up, down, left, right).
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
This is the classic connected-components-on-a-grid problem, solved by flood fill.
Algorithm
Iterate through every cell $(i, j)$ in the grid.
When an unvisited land cell is found, increment the island counter and perform a BFS (or DFS) to mark all reachable land cells as visited.
The final counter equals the number of islands.
Correctness
Each BFS/DFS from an unvisited land cell discovers exactly one maximal connected component, since it visits all cells reachable via 4-adjacency from the starting cell. Two distinct BFS calls never visit the same cell, so each component is counted exactly once.
BFS vs. DFS
BFS (using a queue) avoids the risk of stack overflow on large grids, which can occur with recursive DFS. We use BFS here.
Complexity Analysis
Time: $O(RC)$. Each cell is enqueued and processed at most once.
Space: $O(RC)$ for the visited array. The BFS queue holds at most $O(\min(R, C))$ elements for typical grid shapes, though worst-case it can hold $O(RC)$ elements.
Example
Input (5 x 5):
1 1 0 0 0
1 1 0 0 1
0 0 0 1 1
0 0 0 0 0
1 0 1 0 1
Output: 5The five islands are: $\{(0,0),(0,1),(1,0),(1,1)\}$, $\{(1,4),(2,3),(2,4)\}$, $\{(4,0)\}$, $\{(4,2)\}$, and $\{(4,4)\}$.
Code
C++ solution used for this page.
// IOI 1991 - Problem 1: Island
// Count islands (connected components of 1s) in a 2D grid via BFS.
#include <bits/stdc++.h>
using namespace std;
int R, C;
int grid[505][505];
bool vis[505][505];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
void bfs(int sr, int sc) {
queue<pair<int,int>> q;
q.push({sr, sc});
vis[sr][sc] = true;
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 < R && nc >= 0 && nc < C
&& !vis[nr][nc] && grid[nr][nc] == 1) {
vis[nr][nc] = true;
q.push({nr, nc});
}
}
}
}
int main() {
scanf("%d%d", &R, &C);
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
scanf("%d", &grid[i][j]);
memset(vis, false, sizeof(vis));
int islands = 0;
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
if (grid[i][j] == 1 && !vis[i][j]) {
islands++;
bfs(i, j);
}
printf("%d\n", islands);
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.