MiddleCodeCommonNot answered yet
Count islands of land in a 0/1 grid via flood fill
Given a rectangular grid of 0s (water) and 1s (land), count the islands — maximal groups of land cells connected through 4-directional adjacency (up, down, left, right).
Requirements:
- Each land cell belongs to exactly one island.
- Visit every cell at most a constant number of times.
int countIslands(std::vector<std::vector<int>>& grid) {
// your code here
}Write the implementation.
Scan every cell. On an unvisited land cell, increment the island count and flood-fill its whole connected component with DFS or BFS, marking each reached land cell as visited (e.g. set it to 0). The fill stops at water and borders; each cell is visited a constant number of times.
- ✗Counting each land cell as an island instead of each connected component
- ✗Not marking visited cells, so the same island is counted repeatedly
- ✗Mixing up 4- vs 8-directional adjacency, changing the answer
- →How would 8-directional connectivity change the count?
- →How do you avoid stack overflow on a huge grid with recursive DFS?
Contents
Task
Count land islands in a 0/1 grid (4-directional connectivity) by flood fill.
Solution
#include <vector>
static void flood(std::vector<std::vector<int>>& g, int r, int c) {
if (r < 0 || c < 0 || r >= (int)g.size() || c >= (int)g[0].size() || g[r][c] == 0)
return;
g[r][c] = 0; // mark visited
flood(g, r + 1, c); flood(g, r - 1, c); // four directions
flood(g, r, c + 1); flood(g, r, c - 1);
}
int countIslands(std::vector<std::vector<int>>& grid) {
int count = 0;
for (int r = 0; r < (int)grid.size(); ++r)
for (int c = 0; c < (int)grid[0].size(); ++c)
if (grid[r][c] == 1) { ++count; flood(grid, r, c); }
return count;
}Key points
- Count connected components, not individual land cells.
- The fill marks cells so an island is not counted twice.
- 4- vs 8-directional connectivity changes the answer — clarify it.
Contents
