[Solution] 200. 岛屿数量三解全讲：DFS / BFS / 并查集 + 变式预警（Google 高频）

这题不用多介绍，Google 高频，今年面经里还出现过。更重要的是它爱考变式，只会原题等于白刷。

Part 1 题目
给你一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算岛屿数量。岛屿被水包围，上下左右相连算同一座岛。

Part 2 核心思路：沉岛
看到 '1' 就把整座岛"沉"掉（标成 '0'），数沉了几次就是几座岛。三种写法：

解法一 DFS（最常用）
def numIslands(grid):
    if not grid:
        return 0
    m, n = len(grid), len(grid[0])
    ans = 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)
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                ans += 1
                dfs(i, j)
    return ans
时间 O(m*n)，空间 O(m*n)（最坏递归栈）。

解法二 BFS
from collections import deque
def numIslands_bfs(grid):
    if not grid:
        return 0
    m, n = len(grid), len(grid[0])
    ans = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] != '1':
                continue
            ans += 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 ans
用队列一层层扩，思路一样。怕递归爆栈的面试官会追问这个写法。

解法三 并查集
把相邻的 '1' 合并，最后数有几个集合。代码长，面试里一般不现场写，但提一嘴能加分。

Part 3 易错点
1. 边界检查写全，i<0 这些漏一个就挂。
2. 标记访问：直接把 grid 改成 '0' 最省事，别另开 visited 数组还写错。
3. 递归深度：grid 太大可能爆栈，面试官问起来就说可以换 BFS。

Part 4 变式预警（重点）
只背原题的，变式一出就懵。其它几道都是同一套沉岛思想：
- 695 最大岛屿面积：沉岛时顺手计数，取最大。
- 694 不同岛屿的数量：岛屿形状去重，DFS 路径编码（进/退方向记下来）再判重。
- 827 最大人工岛：先给每座岛编号+算面积，再枚举每个 '0' 翻成 '1' 看能连起多大。
学会一个等于学会一串。

一句话总结：沉岛思想 + 三种写法 + 变式举一反三，这题就算吃透了。

求大米！觉得讲的清楚请赏个米，我继续更 [Solution] 系列。有问题欢迎私信交流。

主楼两段代码的缩进被论坛吞了（纯文本发布行首空格会被吃掉），把格式正确的版本贴在这里：

1. 
   
2. def numIslands(grid):
   
3.     if not grid:
   
4.         return 0
   
5.     m, n = len(grid), len(grid[0])
   
6.     ans = 0
   
7. 
   
8.     def dfs(i, j):
   
9.         if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
   
10.             return
    
11.         grid[i][j] = '0'  # 沉岛
    
12.         dfs(i + 1, j)
    
13.         dfs(i - 1, j)
    
14.         dfs(i, j + 1)
    
15.         dfs(i, j - 1)
    
16. 
    
17.     for i in range(m):
    
18.         for j in range(n):
    
19.             if grid[i][j] == '1':
    
20.                 ans += 1
    
21.                 dfs(i, j)
    
22.     return ans
    

复制代码

1. 
   
2. from collections import deque
   
3. 
   
4. def numIslands_bfs(grid):
   
5.     if not grid:
   
6.         return 0
   
7.     m, n = len(grid), len(grid[0])
   
8.     ans = 0
   
9.     for i in range(m):
   
10.         for j in range(n):
    
11.             if grid[i][j] != '1':
    
12.                 continue
    
13.             ans += 1
    
14.             q = deque([(i, j)])
    
15.             grid[i][j] = '0'
    
16.             while q:
    
17.                 x, y = q.popleft()
    
18.                 for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
    
19.                     nx, ny = x + dx, y + dy
    
20.                     if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':
    
21.                         grid[nx][ny] = '0'
    
22.                         q.append((nx, ny))
    
23.     return ans
    

复制代码