#200
Medium
BFS / DFS
Number of Islands
统计网格中的岛屿数量。
统计网格中的陆地连通块数量。关键动作是：一旦发现一个陆地格子，就立刻把整个岛屿一次性遍历干净。
DFSUnion Find
题目定位
网格本质上就是图：陆地格子与相邻陆地相连，因此这题本质上是在数连通块。
关键观察
只要发现一个陆地格子，就应该一次性把整个连通块都遍历掉。
目标复杂度
O(mn) / O(mn)
这题的解法思路怎么拆
1
逐格扫描整个网格。
2
每当遇到一个尚未访问的陆地格子，岛屿数量加一。
3
从这个格子出发做 DFS 或 BFS，把整个连通块全部标记掉。
4
继续扫描，直到所有陆地都归属于某个已访问岛屿。
拿一个例子顺一遍
1
如果第一行遇到一个 2x2 的陆地块，它整体也只算一个岛屿。
2
DFS 会沿着上下左右四个方向把这个连通块全部标记为已访问。
3
之后再遇到新的独立陆地区域，才会让岛屿数量加到第二个。
参考实现
Pythondef numIslands(grid: list[list[str]]) -> int:
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
def dfs(row: int, col: int) -> None:
if row < 0 or row >= rows or col < 0 or col >= cols:
return
if grid[row][col] != "1":
return
grid[row][col] = "0"
dfs(row + 1, col)
dfs(row - 1, col)
dfs(row, col + 1)
dfs(row, col - 1)
islands = 0
for row in range(rows):
for col in range(cols):
if grid[row][col] == "1":
islands += 1
dfs(row, col)
return islands
常见坑点
warning
visited 打得太晚，导致同一个格子反复被访问。
warning
只检查部分方向，结果少算岛屿。
高频追问
如果改用并查集，思路哪里不同？
如果对角线也算连通，怎么改？
继续刷相关题
先把 BFS / DFS 这个模式刷成体系，再去做更难变体。