200. 岛屿数量

---

题目

描述： 给你一个由 '1'（陆地）和 '0'（水）组成的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外，你可以假设该网格的四条边均被水包围。

示例： 示例 1:

输入: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出: 1

示例 2:

输入: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出: 3

---

解题思路

核心方法

1. 深度优先搜索（DFS）：遍历网格，当遇到 '1' 时，启动 DFS 将所有相连的 '1' 标记为 '0'（避免重复计算），并将岛屿数量加 1。
2. 广度优先搜索（BFS）：使用队列存储相连的 '1'，将其依次标记为 '0'，实现与 DFS 相同的效果。
3. 并查集（Union-Find）：将相连的陆地合并为同一集合，最终统计集合的数量即为岛屿数量。

算法步骤（DFS）

1. 初始化岛屿数量：ans = 0。
2. 遍历网格：对于每个单元格 (i, j)：
   • 若 grid[i][j] == '1'，则 ans++，并启动 DFS。
3. 深度优先搜索：
   • 若当前坐标超出边界或当前单元格为 '0'，直接返回。
   • 将当前单元格标记为 '0'（已访问）。
   • 递归遍历上、下、左、右四个方向的单元格。
4. 返回结果：遍历完成后，返回 ans。

---

代码实现

DFS 实现（Java）

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int ans = 0;
        int rows = grid.length;
        int cols = grid[0].length;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    ans++;
                    dfs(grid, i, j);
                }
            }
        }
        return ans;
    }
    
    public void dfs(char[][] grid, int i, int j) {
        int rows = grid.length;
        int cols = grid[0].length;
        if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] == '0') {
            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);
    }
}

BFS 实现（Java）

import java.util.*;

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int ans = 0;
        int rows = grid.length;
        int cols = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    ans++;
                    queue.offer(new int[]{i, j});
                    grid[i][j] = '0';
                    while (!queue.isEmpty()) {
                        int[] curr = queue.poll();
                        int x = curr[0];
                        int y = curr[1];
                        if (x + 1 < rows && grid[x + 1][y] == '1') {
                            queue.offer(new int[]{x + 1, y});
                            grid[x + 1][y] = '0';
                        }
                        if (x - 1 >= 0 && grid[x - 1][y] == '1') {
                            queue.offer(new int[]{x - 1, y});
                            grid[x - 1][y] = '0';
                        }
                        if (y + 1 < cols && grid[x][y + 1] == '1') {
                            queue.offer(new int[]{x, y + 1});
                            grid[x][y + 1] = '0';
                        }
                        if (y - 1 >= 0 && grid[x][y - 1] == '1') {
                            queue.offer(new int[]{x, y - 1});
                            grid[x][y - 1] = '0';
                        }
                    }
                }
            }
        }
        return ans;
    }
}

---

复杂度分析

DFS / BFS

• 时间复杂度：O(m * n)，其中 m 和 n 分别是网格的行数和列数。每个单元格最多被访问一次。
• 空间复杂度：O(m * n)，最坏情况下（网格全为陆地），DFS 的递归栈或 BFS 的队列大小为 O(m * n)。

---

总结

1. DFS 和 BFS 是解决岛屿数量问题的常用方法，通过标记已访问的陆地避免重复计算，实现简洁高效。
2. DFS 依赖递归栈，BFS 依赖队列，两者时间效率一致，空间效率取决于网格的陆地分布。
3. 并查集方法适合处理动态连通性问题，但实现相对复杂，对于静态网格问题，DFS/BFS 更为常用。

---