企业官网建设流程全解析

题目链接：200. 岛屿数量 - 力扣

这题给一个只包含 '1' 和 '0' 的二维网格：

• '1' 表示陆地。
• '0' 表示水。
• 只有上下左右相邻的陆地才算连在一起，斜着不算。

要求我们求出网格里有多少座岛。

这题表面是在数岛，实际上是在数“连通块”：一整片上下左右连通的陆地，只能算一座岛。

核心思路

遍历整个矩阵。

如果当前位置是水，跳过。

如果当前位置是陆地，但之前已经访问过，说明它已经属于某座岛，也跳过。

只有当当前位置满足：

• 是陆地；
• 并且没有访问过；

才说明我们发现了一座新的岛屿。

这时做两件事：

1. ret++，岛屿数量加一。
2. 从当前位置开始 DFS，把这座岛上所有连通的陆地都标记成已访问。

这样后面外层循环再扫到同一座岛的其他陆地时，因为它们已经被 vis 标记过，就不会重复计数。

为什么 ret++ 放在 DFS 前

外层循环扫到一个“未访问陆地”时，它就是一座新岛的入口。

注意，这里的入口不一定是岛的左上角，也不一定是什么特殊位置。只要它还没访问过，就说明前面没有任何一次 DFS 处理过它所在的岛。

所以此时可以直接 ret++。

然后再调用 dfs(grid, i, j)，把这座岛整体标记掉。

可以把两层逻辑分开看：

• 外层循环：负责发现新岛入口。
• DFS：负责从入口出发，把同一座岛全部处理完。

DFS 函数负责什么

这篇代码用的是 vis 数组，不是直接修改 grid。

所以所谓“把岛变成海洋”，在这份代码里更准确地说，是把同一座岛上的陆地全部标记为“已访问”。

也就是：

vis[i][j] = true;

然后向上下左右四个方向继续找陆地。

四个方向可以用两个数组表示：

int[] dx = {0, 0, -1, 1};

int[] dy = {1, -1, 0, 0};

对应的顺序是：右、左、上、下。

每次从当前位置 (i, j) 走到新位置：

int x = i + dx[k];

int y = j + dy[k];

只有当新位置同时满足下面几个条件时，才继续递归：

• 坐标没有越界；
• 没有访问过；
• grid[x][y] == '1'，也就是它确实是陆地。

Java 代码

class Solution {

boolean[][] vis;

int m, n;

int[] dx = {0, 0, -1, 1};

int[] dy = {1, -1, 0, 0};

public int numIslands(char[][] grid) {

m = grid.length;

n = grid[0].length;

vis = new boolean[m][n];

int ret = 0;

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

if (!vis[i][j] && grid[i][j] == '1') {

ret++;

dfs(grid, i, j);

}

}

}

return ret;

}

public void dfs(char[][] grid, int i, int j) {

vis[i][j] = true;

for (int k = 0; k < 4; k++) {

int x = i + dx[k];

int y = j + dy[k];

if (x >= 0 && x < m

&& y >= 0 && y < n

&& !vis[x][y]

&& grid[x][y] == '1') {

dfs(grid, x, y);

}

}

}

}

看图理解递归展开

先看运行结果：

再看递归展开和逻辑展开：

这张图重点看两个地方。

第一个是左边代码里的 dfs(grid, x, y)。

当递归走到一个新的陆地位置时，第一件事就是把它标记为已访问：

vis[i][j] = true;

也就是说，这个位置以后不会再次成为“新岛入口”。

第二个是右边样例里的扫描顺序。

外层循环仍然会一格一格往后扫，但扫到已经访问过的陆地时，条件：

!vis[i][j] && grid[i][j] == '1'

不会再成立。

这就是为什么同一座岛不会重复计数。

一个容易混的细节

原地修改 grid 和使用 vis 数组，本质上都是为了避免重复访问。

有些题解会在 DFS 时把陆地改成水：

grid[i][j] = '0';

这相当于“访问过的陆地不再当陆地看”。

而这篇代码没有改原数组，而是用了 vis：

vis[i][j] = true;

所以理解时不要被“变成海洋”这句话卡住。这里真正的意思是：这块陆地已经被当前这次 DFS 处理过了，后面不能再重复处理。

易错点

1. 斜对角不算连通。

题目只允许上下左右相邻，所以方向数组只有四个方向。

1. ret++ 要放在发现新岛入口时。

也就是外层循环遇到“未访问陆地”时加一，而不是 DFS 每走到一个陆地就加一。

1. vis[i][j] = true 不需要回溯。

这不是排列组合那种“选完还要撤销”的 DFS。这里访问过就是真的处理完了，不能回退成没访问。

1. 坐标合法性要先判断。

访问 grid[x][y] 和 vis[x][y] 前，必须先保证 x、y 没越界。

总结

这题的关键不是“会不会写 DFS”，而是想清楚 DFS 在这里承担的任务。

外层循环负责找入口。

DFS 负责从入口出发，把同一座岛的所有陆地都标记为已访问。

所以，记住：

• 相信你的递归函数，它可以把当前岛处理完。
• 不理解时，先手动展开一两个样例。
• 等手动展开通了，再把这个过程抽象成 DFS。

当你能理解这一点，这类岛屿问题，比如岛屿最大面积、图像渲染、被围绕的区域，思路就会顺很多。