岛屿数量问题

题目描述
给定一个由 '1'（陆地）和 '0'（水）组成的二维网格地图，计算网格中岛屿的数量。一个岛屿被水包围，并且通过水平方向或垂直方向上相邻的陆地连接形成。你可以假设网格的四个边均被水包围。

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

详细解题步骤

1. 理解问题核心
   岛屿是由相邻的 '1' 组成的连通区域，相邻指上下左右四个方向。目标是统计这样的连通区域个数。这本质上是在二维矩阵中寻找连通分量的数量，可以用深度优先搜索（DFS）、广度优先搜索（BFS）或并查集（Union-Find）解决。

2. DFS 解法思路

   • 遍历整个网格，对每个格子进行检查。
   • 如果当前格子是 '1'，说明发现了一个新岛屿，于是：
     1. 将岛屿数量加一。
     2. 对这个格子进行 DFS，把与它相连的所有陆地（即上下左右方向上的 '1'）都标记为已访问，避免重复计数。
   • 如何标记已访问？可以直接将访问过的 '1' 改成 '0' 或一个特殊字符（如 '#'），这样后续遍历就不会再把它当成新岛屿的起点了。

3. DFS 递归函数的细节

   • 函数定义：dfs(grid, i, j)，其中 (i, j) 是当前格子的坐标。
   • 递归终止条件：
     1. 坐标越界（超出网格范围）。
     2. 当前格子是 '0'（水）或已访问过的格子。
   • 递归过程：
     1. 将当前格子标记为已访问（如 grid[i][j] = '0'）。
     2. 对当前格子的四个方向（上、下、左、右）分别递归调用 DFS。

4. 方向数组的使用
   为了代码简洁，可以定义一个方向数组：
   directions = [(0,1), (0,-1), (1,0), (-1,0)]
   分别对应右、左、下、上四个方向。在递归中，通过循环遍历这四个方向，生成新坐标 (ni, nj)，然后递归调用。

5. 完整算法步骤

   1. 初始化岛屿数量 count = 0。
   2. 遍历网格的每个格子 (i, j)：
      • 如果 grid[i][j] == '1'：
        • count++
        • 调用 dfs(grid, i, j) 将整个岛屿标记掉。
   3. 返回 count。

6. 复杂度分析

   • 时间复杂度：O(M×N)，其中 M 是行数，N 是列数。每个格子最多被访问一次。
   • 空间复杂度：O(M×N)（最坏情况下递归栈的深度，例如整个网格都是陆地时）。

7. BFS 解法简介
   也可以用队列实现 BFS 来替代 DFS 的递归过程：

   • 当遇到 '1' 时，将其入队，然后不断取出队首元素，将其四个方向中为 '1' 的邻居入队并标记，直到队列为空。
   • BFS 的空间复杂度在最坏情况下也是 O(M×N)（队列可能存储较多节点）。

8. 并查集解法思路

   • 将每个 '1' 的格子视为一个独立的集合。
   • 遍历网格，对每个 '1' 的格子，检查其右侧和下侧的格子（避免重复检查），如果也是 '1'，则将它们合并到同一个集合。
   • 最终，岛屿数量 = 集合的总数 - 水的格子所在的集合数（通常水的格子单独视为一个集合，或不计入）。实际实现时，可以只统计 '1' 的格子在并查集中的根节点个数。

9. 总结
   岛屿数量问题是二维矩阵中连通分量计数的经典问题，DFS/BFS 是直观解法，并查集在需要动态合并的场景中更高效。关键在于理解如何通过搜索或合并来标记整个连通区域，避免重复计数。