The Number of Islands – Task and Solution (BFS/DFS)
A classic search task in a matrix: count the connected regions. It is solved with a breadth-first (BFS) or depth-first (DFS) traversal of a graph, where the cells of the matrix are the nodes, and neighbouring cells are connected by an edge.
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.
The task
A map is a matrix with n rows and m columns (n, m ≤ 1000): the character # is land, and . is water. An island is a set of land cells connected by their sides (up, down, left, right). How many islands are there and what is the area of the largest one?
Example
Input
4 5
##..#
#...#
..#..
.....Output
3
3The islands are: {(0,0), (0,1), (1,0)} with the area 3, {(0,4), (1,4)} with the area 2 and {(2,2)} with the area 1.
The idea of the solution
We go through all the cells. When we come across land that has not been visited yet, we have found a new island: we increase the counter and from that cell we start a BFS that marks ("floods") all the cells of that island and counts them. Every cell is marked exactly once, so the complexity is O(n · m).
A recursive DFS is shorter, but for a 1000 × 1000 map the depth of the recursion can reach a million calls and overflow the stack – that is why BFS with a queue is used here.
Solution (C++)
#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<string> grid(n);
for (auto &row : grid) cin >> row;
vector<vector<bool>> visited(n, vector<bool>(m, false));
int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
int islands = 0, largest = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (grid[i][j] != '#' || visited[i][j]) continue;
islands++; // a new island
int area = 0;
queue<pair<int, int>> q;
q.push({i, j});
visited[i][j] = true;
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
area++;
for (int s = 0; s < 4; s++) {
int nr = r + dr[s], nc = c + dc[s];
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
if (grid[nr][nc] != '#' || visited[nr][nc]) continue;
visited[nr][nc] = true; // mark it when it is put into the queue
q.push({nr, nc});
}
}
largest = max(largest, area);
}
cout << islands << "\n" << largest << endl;
return 0;
}
A cell is marked as visited at the moment it is put into the queue, not when it is taken out – otherwise the same cell could enter the queue several times.
Variants
- If diagonal neighbours also count, the arrays of moves have 8 elements.
- "How many islands are there after every addition of land" – then a Disjoint Set Union is used.
- The same task on LeetCode: Number of Islands.
- Check the borders of the matrix before accessing a cell.
- In BFS mark a cell when you put it into the queue.
- For large maps avoid deep recursion – use a queue (BFS) or your own stack.
Check your knowledge
Open the quiz
Mini quiz: the number of islands
1. What is the complexity of the solution for an n × m map?
2. Why is BFS recommended instead of a recursive DFS for a 1000 × 1000 map?
