尧图网页设计 
题目链接200. 岛屿数量 - 力扣这题给一个只包含 1 和 0 的二维网格1 表示陆地。0 表示水。只有上下左右相邻的陆地才算连在一起斜着不算。要求我们求出网格里有多少座岛。这题表面是在数岛实际上是在数“连通块”一整片上下左右连通的陆地只能算一座岛。核心思路遍历整个矩阵。如果当前位置是水跳过。如果当前位置是陆地但之前已经访问过说明它已经属于某座岛也跳过。只有当当前位置满足是陆地并且没有访问过才说明我们发现了一座新的岛屿。这时做两件事ret岛屿数量加一。从当前位置开始 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;这相当于“访问过的陆地不再当陆地看”。而这篇代码没有改原数组而是用了 visvis[i][j] true;所以理解时不要被“变成海洋”这句话卡住。这里真正的意思是这块陆地已经被当前这次 DFS 处理过了后面不能再重复处理。易错点斜对角不算连通。题目只允许上下左右相邻所以方向数组只有四个方向。ret 要放在发现新岛入口时。也就是外层循环遇到“未访问陆地”时加一而不是 DFS 每走到一个陆地就加一。vis[i][j] true 不需要回溯。这不是排列组合那种“选完还要撤销”的 DFS。这里访问过就是真的处理完了不能回退成没访问。坐标合法性要先判断。访问 grid[x][y] 和 vis[x][y] 前必须先保证 x、y 没越界。总结这题的关键不是“会不会写 DFS”而是想清楚 DFS 在这里承担的任务。外层循环负责找入口。DFS 负责从入口出发把同一座岛的所有陆地都标记为已访问。所以记住相信你的递归函数它可以把当前岛处理完。不理解时先手动展开一两个样例。等手动展开通了再把这个过程抽象成 DFS。当你能理解这一点这类岛屿问题比如岛屿最大面积、图像渲染、被围绕的区域思路就会顺很多。 岛屿数量：DFS + vis 数组为什么不会重复计数
题目链接200. 岛屿数量 - 力扣这题给一个只包含 1 和 0 的二维网格1 表示陆地。0 表示水。只有上下左右相邻的陆地才算连在一起斜着不算。要求我们求出网格里有多少座岛。这题表面是在数岛实际上是在数“连通块”一整片上下左右连通的陆地只能算一座岛。核心思路遍历整个矩阵。如果当前位置是水跳过。如果当前位置是陆地但之前已经访问过说明它已经属于某座岛也跳过。只有当当前位置满足是陆地并且没有访问过才说明我们发现了一座新的岛屿。这时做两件事ret岛屿数量加一。从当前位置开始 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;这相当于“访问过的陆地不再当陆地看”。而这篇代码没有改原数组而是用了 visvis[i][j] true;所以理解时不要被“变成海洋”这句话卡住。这里真正的意思是这块陆地已经被当前这次 DFS 处理过了后面不能再重复处理。易错点斜对角不算连通。题目只允许上下左右相邻所以方向数组只有四个方向。ret 要放在发现新岛入口时。也就是外层循环遇到“未访问陆地”时加一而不是 DFS 每走到一个陆地就加一。vis[i][j] true 不需要回溯。这不是排列组合那种“选完还要撤销”的 DFS。这里访问过就是真的处理完了不能回退成没访问。坐标合法性要先判断。访问 grid[x][y] 和 vis[x][y] 前必须先保证 x、y 没越界。总结这题的关键不是“会不会写 DFS”而是想清楚 DFS 在这里承担的任务。外层循环负责找入口。DFS 负责从入口出发把同一座岛的所有陆地都标记为已访问。所以记住相信你的递归函数它可以把当前岛处理完。不理解时先手动展开一两个样例。等手动展开通了再把这个过程抽象成 DFS。当你能理解这一点这类岛屿问题比如岛屿最大面积、图像渲染、被围绕的区域思路就会顺很多。