Number of Islands
A grid contains 1 for land and 0 for water. An island is a maximal group of land cells connected horizontally or vertically. Count the islands.
- 1 ≤ m, n ≤ 300
- grid[i][j] ∈ {0, 1}
- Grid where cells are nodes and 4-neighbours are edges
- Counting connected components
- Flood fill from every unvisited land cell
BFS explores in rings of increasing distance, so the first time it reaches a node it has found a shortest path in terms of edge count. "Minimum number of moves" on any state space where each move costs 1 is BFS, whether the states are grid cells, words, or puzzle configurations.
Scan every cell. When an unvisited land cell is found, increment the count and flood-fill from it with BFS (queue of cells), marking each reached land cell as visited by overwriting it with water or a visited flag. Each flood fill consumes one whole island, so the number of fills equals the number of islands. Every cell is enqueued at most once.
- Recursive DFS is shorter but risks stack overflow on 300×300 snakes. Union-find also works and is preferable when cells are added over time.