BM57. 岛屿数量
题目描述
给一个 01 矩阵，1 代表陆地，0 代表海洋，上下左右相邻的 1 属于同一个岛。
判断岛屿个数。（存储的 01 数据其实是字符 '0'、'1'。）
输入格式
grid：字符型二维数组，只含0与1。
输出格式
返回 int 型，岛屿的数量。
示例
示例 1
输入：
grid = [[1,1,0,0,0],[0,1,0,1,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,1,1,1]]
输出：
3
说明： 左上角一片、右侧一片、下方一片，共 3 座岛。
示例 2
输入：
grid = [[0]]
输出：
0
说明： 全是海洋，没有岛。
示例 3
输入：
grid = [[1,1],[1,1]]
输出：
1
说明： 四格相连，是一整座岛。
解题思路
第一步：理解问题本质
「岛屿」= 四联通的 1 组成的连通块。求连通块的数量，
就是经典的「网格洪水填充 / Flood Fill」问题。
第二步：遍历 + DFS 淹没
扫描每个格子：
- 遇到一个还没访问过的陆地，就说明发现了一座新岛（数量 +1）；
- 立刻从它出发做一次 DFS/BFS，把所有相连的陆地都标记成「已访问」， 相当于把这座岛「淹没」，之后就不会重复计数。
「发现一座岛，就淹没一整片」，是这个模板的核心。
第三步：两种实现
- DFS：递归或栈。递归写法最短，但大网格可能爆栈， 用显式栈（迭代 DFS）更稳。
- BFS：队列，天然不会爆栈，适合连通块特别大的情况。
两者复杂度一样，都是 O(rows × cols)。
一个细节：题面说「存储的 01 数据其实是字符」，但示例又写成整数。
稳妥起见，判断陆地时同时接受 '1' 和 1，并用独立的 seen 数组标记，
不去修改入参。
完整代码实现
算法可视化 · 逐帧回放这道题的代码306 帧 · 录制输入 [[1,1,0,0,0],[0,1,0,1,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,1,1,1]]
from typing import List
class Solution:
def solve(self, grid: List[List[str]]) -> int:
"""统计 01 矩阵里的四联通岛屿数量"""
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
count = 0
def is_land(i: int, j: int) -> bool:
# 兼容字符 '1' 与整数 1 两种入参
return not seen[i][j] and grid[i][j] in ('1', 1)
for i in range(rows):
for j in range(cols):
if is_land(i, j):
count += 1 # 发现新岛
seen[i][j] = True
stack = [(i, j)]
while stack: # 淹没整座岛
x, y = stack.pop()
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if 0 <= nx < rows and 0 <= ny < cols and is_land(nx, ny):
seen[nx][ny] = True
stack.append((nx, ny))
return count
示例推演
以示例 1 的矩阵为例：
1 1 0 0 0
0 1 0 1 1
0 0 0 1 1
0 0 0 0 0
0 0 1 1 1
| 扫描到的第一个未访问陆地 | 淹没的格子 | 岛屿数 |
|---|---|---|
| (1,1) | (1,1)(1,2)(2,2) | 1 |
| (2,4) | (2,4)(2,5)(3,4)(3,5) | 2 |
| (5,3) | (5,3)(5,4)(5,5)(4,3)(4,4) | 3 |
扫描结束，答案为 3。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| DFS（迭代栈） | O(rows*cols) | O(rows*cols) | 推荐 |
| BFS | O(rows*cols) | O(rows*cols) | 大块连通时更稳 |
易错点总结
1. 忘记标记已访问
不标记会让同一座岛被反复计数，或在 DFS 里无限打转。
2. 入参类型不统一
题面说是字符，示例写成整数。用 in ('1', 1) 兼容两者，
不要硬写 == '1'。
3. 只考虑四联通
只算上下左右，不算对角线。八个方向会把「斜挨着的两座岛」误当成一座。
扩展思考
- 若要求「最大岛屿面积」，把发现岛时的计数改成统计淹没的格子数并取最大。
- 「封闭岛屿」（不接触边界的岛）只需在淹没时判断是否碰到边界。
- 同类问题还可以用并查集合并相邻陆地来求解。