200. 岛屿数量 (Medium)
专题归类： 07-图论 LeetCode 链接： https://leetcode.cn/problems/number-of-islands/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个由 '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
题目详细分析
- 数据范围： m grid.length, n grid[i].length，1 ≤ m, n ≤ 300。网格最大可达 300×300 = 90,000 个格子。
- 输入输出特征： 只有
'1'和'0'两种字符，不区分大小写。岛屿由上下左右四方向相邻的'1'组成（对角线不算）。 - 边界条件： 空网格不会出现（至少 1×1）。网格四边之外都是水，不需要额外处理边界外的逻辑，但代码必须做边界检查。
- 核心约束： 不允许原地修改网格？不，题目没说不能修改，因此可以用「沉岛法」原地标记，将访问过的
'1'改为'0'来节省 visited 数组。 - 隐藏条件： 如果网格全部是
'0'，返回 0。如果全部是'1'，返回 1。
小白版直白理解
想象你坐在直升机上俯瞰一片海洋，海面上有很多小岛。海水用 0 表示，陆地用 1 表示。你要数清楚有多少块独立的陆地。
你怎么数？一块一块来：看到一块没去过的陆地，就跳上去，然后把这块陆地以及所有和它连着的陆地都走一遍（标记为”已去过”），计数加 1。接着继续飞，找下一块没去过的陆地，重复操作。最后数出来的数字就是岛屿数量。
这里的「走一遍」就是 DFS（一条路走到黑，走完四周）或 BFS（一层一层往外扩散）。
解题思路
思路一：DFS 沉岛法（推荐）
核心思想： 遍历每个格子，遇到 '1' 就启动 DFS，把当前格子以及所有与其相连的 '1' 都标记为 '0'（沉岛），然后岛屿计数加 1。这样每个格子最多被访问一次。
为什么 DFS 可行？因为岛屿的形状不管多复杂，只要四方向相连都属于同一岛屿。DFS 可以沿着一条分支深入到底，再回溯探索其他分支，恰好覆盖整块相连区域。
def numIslands(grid):
if not grid:
return 0
m, n = len(grid), len(grid[0])
def dfs(i, j):
# 超出边界 或 当前是水/已访问
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
return
grid[i][j] = '0' # 沉岛：标记为已访问
dfs(i + 1, j) # 下
dfs(i - 1, j) # 上
dfs(i, j + 1) # 右
dfs(i, j - 1) # 左
count = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1': # 发现新岛屿
count += 1
dfs(i, j) # 沉掉整座岛
return count复杂度： 时间 O(m×n)，空间 O(m×n)（最坏递归深度）
思路二：BFS 沉岛法
用队列代替递归，避免递归栈溢出。同样遍历网格，遇到 '1' 就 BFS 扩散沉岛。
from collections import deque
def numIslands(grid):
if not grid:
return 0
m, n = len(grid), len(grid[0])
count = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
count += 1
q = deque([(i, j)])
grid[i][j] = '0' # 入队即标记
while q:
x, y = q.popleft()
for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':
grid[nx][ny] = '0'
q.append((nx, ny))
return count复杂度： 时间 O(m×n)，空间 O(min(m,n))（队列最坏宽度）
思路三：并查集（Union-Find）
将每个 '1' 视为一个节点，相邻的 '1' 合并到同一集合。最后统计有多少个集合根节点是 '1'。
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return
if self.rank[rx] < self.rank[ry]:
self.parent[rx] = ry
elif self.rank[rx] > self.rank[ry]:
self.parent[ry] = rx
else:
self.parent[ry] = rx
self.rank[rx] += 1
def numIslands(grid):
if not grid:
return 0
m, n = len(grid), len(grid[0])
uf = UnionFind(m * n)
directions = [(1,0), (-1,0), (0,1), (0,-1)]
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
idx = i * n + j
for di, dj in directions:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == '1':
uf.union(idx, ni * n + nj)
# 统计所有 '1' 的根节点（去重）
roots = set()
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
roots.add(uf.find(i * n + j))
return len(roots)复杂度： 时间 O(m×n × α(mn))，空间 O(m×n)
易错点
- 边界越界： 递归 DFS 时一定要先检查行列索引是否在有效范围内，否则会报 IndexError。
- 重复访问： 必须及时标记已访问，避免死循环（上下左右来回走）。DFS 在调用递归前就应该标记，BFS 在入队时就要标记，不要等到出队时再标记。
- 递归深度爆栈： 极端情况下（整个网格全是
'1'），DFS 递归深度可达 90,000 层，Python 会 RecursionError。此时应改用 BFS 或手动设置sys.setrecursionlimit()。 - 行列顺序：
grid[i][j]中 i 是行号（纵坐标），j 是列号（横坐标），四方向遍历时注意 dx 对应行变化。 - 原地修改副作用： 沉岛法会直接修改原输入数组，如果不允许修改原数组，需要额外 visited 矩阵。
框架提炼
网格 DFS 模板（四方向）：
def grid_dfs(grid):
def dfs(i, j):
# 1. 边界 + 有效性检查
if i < 0 or i >= m or j < 0 or j >= n or visited[i][j] or grid[i][j] != target:
return
visited[i][j] = True # 2. 标记已访问
# 3. 四方向递归
dfs(i+1, j); dfs(i-1, j)
dfs(i, j+1); dfs(i, j-1)
m, n = len(grid), len(grid[0])
visited = [[False] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if not visited[i][j] and grid[i][j] == target:
dfs(i, j) # 或在这里计数网格 BFS 模板：
def grid_bfs(grid):
from collections import deque
m, n = len(grid), len(grid[0])
visited = [[False] * n for _ in range(m)]
q = deque()
while q:
i, j = q.popleft()
for di, dj in [(1,0),(-1,0),(0,1),(0,-1)]:
ni, nj = i+di, j+dj
if 0 <= ni < m and 0 <= nj < n and not visited[ni][nj] and grid[ni][nj] == target:
visited[ni][nj] = True
q.append((ni, nj))关联题目
- 994-腐烂的橘子 — 同一网格四方向扩散模型，但本题是 DFS 找连通分量，994 是多源 BFS 求最短扩散时间。
- 207-课程表 — 图论的另一种题目：有向图拓扑排序，与岛屿的网格图遍历互为补充。
- 130-被围绕的区域 — 也是网格 DFS，但边界条件处理更复杂（从边界 O 出发 DFS，标记未被包围的区域）。