LeetCode 200. 岛屿数量

题目描述
给你一个由 '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'）组成的连通分量。相邻指上下左右四个方向。
• 目标：统计网格中连通分量的个数。
• 关键：遍历网格，当遇到一个未被访问的 '1'，就探索整个连通区域（标记为已访问），同时岛屿计数加一。

2. 算法选择：深度优先搜索（DFS）

• 从某个陆地单元格出发，递归访问其上下左右的相邻陆地，直到所有相连的陆地都被访问。
• 访问过的陆地标记为 '0'（或单独维护访问数组），避免重复计数。

3. 详细步骤

1. 初始化计数器：count = 0。
2. 遍历网格：对每个单元格 (i, j)：
   • 如果当前单元格是 '1'（陆地）：
     • 调用 DFS 函数，探索并标记所有相连的陆地。
     • 岛屿计数 count += 1。
3. DFS 函数设计：
   • 基础情况：如果当前位置超出网格边界，或当前单元格是 '0'（水），则返回。
   • 标记当前单元格为已访问（例如，将 '1' 改为 '0'）。
   • 递归访问上下左右四个方向：
     • (i-1, j)（上）
     • (i+1, j)（下）
     • (i, j-1)（左）
     • (i, j+1)（右）

4. 示例演示
以示例网格为例：

• 遍历到 (0,0) 的 '1'，DFS 探索并标记整个左上角 2x2 的陆地，计数变为 1。
• 之后跳过已标记的 '0'，直到 (2,2) 的 '1'，探索并标记中间的小岛，计数变为 2。
• 最后在 (3,3) 发现 '1'，探索右下角两个相连的陆地，计数变为 3。

5. 复杂度分析

• 时间复杂度：O(m×n)，每个单元格最多被访问一次。
• 空间复杂度：O(m×n)（DFS 递归栈的最坏情况，如网格全为陆地）。

6. 边界情况

• 网格全为水：返回 0。
• 网格全为陆地：返回 1。
• 单行或单列网格：算法依然适用。

通过以上步骤，即可正确统计岛屿数量。