LeetCode 200中等网格 · DFS
岛屿数量 图解题解
这道题到底在问什么
网格里 1 是陆地、0 是水。上下左右相连的 1 算同一座岛，问共几座岛？
- grid
- 见下方（3×3）
- 输出
- 2
最优解：一步一步想明白
- 31=陆地, 0=水绿色是陆地，蓝色是水。肉眼看：左上角连成一片是一座岛，右下角单独一格是另一座。
- 4从左到右、从上到下扫网格。每碰到一个还没访问过的陆地，岛屿数就 +1，然后用 DFS 把和它相连的陆地全部标记为已访问，这样同一座岛就不会被重复数。
- 5是陆地 → 先 DFS扫到 (0,0) 是陆地，而且没访问过。按代码的顺序：先对它 DFS，把整座岛淹掉，等 DFS 结束再给岛屿数 +1。
- 6标记已访问，看四周把 (0,0) 标记为已访问（变灰）。然后检查它的上下左右，看哪些也是陆地。
- 7是陆地 → 继续深入(0,0) 右边的 (0,1) 是陆地，走过去，继续对它做 DFS。
- 8四周无新陆地标记 (0,1)。它右边是水、下边是水，没有新陆地可走，退回 (0,0) 继续看其它方向。
- 9是陆地 → 深入(0,0) 下边的 (1,0) 也是陆地，走过去。
- 10四周无新陆地标记 (1,0)。它周围也没有新陆地了。这座岛的 3 格全部访问完，DFS 结束。
- 11count++ 不在每个陆地格，而在「启动一次新 DFS」时这是这道题的灵魂。刚才一次 DFS 从 (0,0) 出发，把和它连通的 3 格陆地全部淹成已访问，整座岛一次性沉没。DFS 返回后，岛屿数才 +1。所以记住：count 不是每遇到一格陆地就加，而是「外层扫描每启动一次新的 DFS」才加一次——一次 DFS = 一座岛 = 加一。淹岛的作用，就是保证同一座岛不会被重复数。
- 12跳过 0接着扫 (0,2)、(1,1)、(1,2)、(2,0)、(2,1)——它们要么是水、要么已访问，全部跳过。
- 13是陆地 → 先 DFS扫到 (2,2) 是陆地，又没访问过。同样：先对它 DFS。
- 14孤岛，DFS 结束 → count=2标记 (2,2)。上边是水、左边是水、右和下都越界，是孤零零一座岛，DFS 立刻结束。岛屿数 +1 = 2。
- 15岛屿数 = 2整个网格扫完，一共触发了 2 次「发现新岛」，答案就是 2。
- 16DFS 沿着一个方向一直深入，直到走不动（碰到水或边界）才回头换方向。把一座岛「淹没」靠的就是它。
- 20岛屿最大面积、被围绕的区域、单词搜索……所有「网格里找连通区域」的题，都是这套网格 DFS/BFS。
- 26① DFS 还是 BFS？——都行：DFS 用递归/栈一条路走到黑，BFS 用队列一圈圈扩散，复杂度一样。② 能不开 visited 吗？——能，直接把走过的陆地改成水 0 原地标记，省空间。③ 空间为什么 O(m×n)？——最坏整张图都是陆地，递归栈 / 队列会压满。
- 27「碰到没访问的就 DFS 染整片」是所有网格连通块题的骨架：LC695 岛屿最大面积（dfs 返回格子数）、LC994 腐烂橘子（改 BFS 多源扩散）、LC130 被围绕的区域——只换「DFS 里做什么」。更多在 图 / 搜索专题 继续。
⚠️ 容易写错的地方
✗ 错：递归前不判越界
✓ 对：先判 0<=ni＜m and 0<=nj＜n
边缘格子的邻居会出界
✗ 错：忘了标记 visited
✓ 对：进 dfs 第一件事就标记
否则无限递归 / 重复数同一座岛
完整代码（Python / C++ / Java）
Python
class Solution:
def numIslands(self, grid):
m, n = len(grid), len(grid[0])
def dfs(r, c):
if r<0 or r>=m or c<0 or c>=n or grid[r][c]!='1': return
grid[r][c] = '0' # 淹掉，当标记
dfs(r,c+1); dfs(r+1,c); dfs(r-1,c); dfs(r,c-1)
ans = 0
for r in range(m):
for c in range(n):
if grid[r][c] == '1':
dfs(r, c); ans += 1 # 淹完整座岛，再 +1
return ansC++
class Solution {
int m, n;
void dfs(vector<vector<char>>& g, int r, int c) {
if (r<0||r>=m||c<0||c>=n||g[r][c]!='1') return;
g[r][c] = '0'; // 淹掉，当标记
dfs(g,r,c+1); dfs(g,r+1,c); dfs(g,r-1,c); dfs(g,r,c-1);
}
public:
int numIslands(vector<vector<char>>& g) {
m = g.size(); n = g[0].size(); int ans = 0;
for (int r=0;r<m;r++) for (int c=0;c<n;c++)
if (g[r][c]=='1') { dfs(g,r,c); ans++; }
return ans;
}
};Java
class Solution {
int m, n;
public int numIslands(char[][] g) {
m = g.length; n = g[0].length; int ans = 0;
for (int r=0;r<m;r++) for (int c=0;c<n;c++)
if (g[r][c]=='1') { dfs(g,r,c); ans++; }
return ans;
}
void dfs(char[][] g, int r, int c) {
if (r<0||r>=m||c<0||c>=n||g[r][c]!='1') return;
g[r][c] = '0'; // 淹掉，当标记
dfs(g,r,c+1); dfs(g,r+1,c); dfs(g,r-1,c); dfs(g,r,c-1);
}
}套路模板 · 网格 DFS
for i in range(m):
for j in range(n):
if grid[i][j] == "1": # 发现新岛
dfs(grid, i, j) # 淹掉整座岛
ans += 1 # 一次 DFS = 一座岛
def dfs(grid, i, j):
if not (0 <= i < m and 0 <= j < n) or grid[i][j] != "1":
return
grid[i][j] = "0" # 淹掉=标记已访问
dfs(grid, i, j+1); dfs(grid, i+1, j)
dfs(grid, i-1, j); dfs(grid, i, j-1)class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size(), n = grid[0].size();
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
ans++;
dfs(grid, i, j);
}
}
}
return ans;
}
void dfs(vector<vector<char>>& grid, int i, int j) {
int m = grid.size(), n = grid[0].size();
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') return;
grid[i][j] = '0';
dfs(grid, i, j + 1); dfs(grid, i + 1, j);
dfs(grid, i - 1, j); dfs(grid, i, j - 1);
}
};class Solution {
private int m, n;
public int numIslands(char[][] grid) {
m = grid.length; n = grid[0].length;
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
ans++;
dfs(grid, i, j);
}
}
}
return ans;
}
private void dfs(char[][] grid, int i, int j) {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') return;
grid[i][j] = '0';
dfs(grid, i, j + 1); dfs(grid, i + 1, j);
dfs(grid, i - 1, j); dfs(grid, i, j - 1);
}
}复杂度
时间复杂度
O(m×n)
每个格子最多访问一次
空间复杂度
O(m×n)
递归栈最坏铺满整张网格
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 岛屿数量 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
DFS 的访问标记放哪？+
进入格子后立刻标记或改成水，避免四方向递归绕回来。
为什么斜着不连通？+
题目只定义上下左右四方向连通，斜边不能合并岛屿。
复杂度怎么说？+
每个格子最多访问一次，时间 O(mn)，递归栈最坏 O(mn)。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。