岛屿数量

Problem

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]] Output: 1

Example 2:

Input: grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]] Output: 3

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

Idea

Treat the grid as a graph where each land cell is connected to its land neighbors in the four directions, and count the connected components with depth-first search (flood fill).

Scan every cell. When an unvisited '1' is found, it starts a new island, so increase the count and run DFS from it to sink the whole island by turning every connected '1' into '0'. Each land cell is sunk only once, so later scans skip it.

Time complexity: \(O(mn)\), Space complexity: \(O(mn)\) for the recursion stack in the worst case

Pseudo Code

count = 0;
for (i = 0; i < m; i++) {
    for (j = 0; j < n; j++) {
        if (grid[i][j] == '1') {
            count++;
            dfs(grid, i, j);
        }
    }
}
return count;

dfs(grid, i, j) {
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') {
        return;
    }
    grid[i][j] = '0';
    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}