DFS连通域统计：岛屿数量问题及其变形

0.前言本文我们来学习一下算法题中颇为著名的岛屿数量问题我将会从问题本身入手详细分析解题思路给出完整代码并进行解析最后简单了解一下几个岛屿问题的变种题目。1. 问题描述题目给出一个只含有 0 和 1 矩阵1 代表是陆地0 代表海洋 如果两个 1 相邻那么这两个 1 属于同一个岛我们暂时只考虑上下左右为相邻。上下左右相邻的陆地可以组成一个岛屿我们的目标是计算岛屿的个数。当输入为下图的矩阵时共有三个岛屿因此输出应该为 3 。2. 解题思路当题目给出一个M × N的矩阵时我们需要找出岛屿个数可以考虑如下思路从矩阵的第一行第一个元素开始遍历直到遍历完整个矩阵。当遍历到0时直接跳过。每当遍历到一个1时说明找到了一个岛屿将岛屿数量加 1然后将这个1修改为0。此外还需要使用 DFS 从该位置开始向上下左右四个方向分别遍历一样是遇到0就跳过遇到1就改成0这时不需要在将岛屿数量加一了因为我们现在处理的是第一次发现的那个子岛屿的相邻岛屿他们整体只算一个岛屿这样能够保证不会重复计数。3. 完整代码classSolution{public:voiddfs(vectorvectorchargrid,intr,intc){intnrgrid.size();intncgrid[0].size();//如果越界或者遇到0就直接返回if(r0||rnr||c0||cnc||grid[r][c]0){return;}//能走到这说明遇到1了把它改成0grid[r][c]0;//向上下左右四个方向继续找找到了继续改dfs(grid,r,c-1);dfs(grid,r,c1);dfs(grid,r-1,c);dfs(grid,r1,c);}intsolve(vectorvectorchargrid){intnrgrid.size();if(nr0)return0;intncgrid[0].size();intisland_num0;for(intr0;rnr;r){for(intc0;cnc;c){if(grid[r][c]1){//只需要在主循环中第一次遇见1时将岛屿数量加一//dfs会把这个1上下左右连通的1全部改成0,防止重复计数island_num;dfs(grid,r,c);}}}returnisland_num;}};4. 代码执行流程详解为了能够更加深入地了解代码的执行过程我以下面的矩阵为例详细分析一下程序开始时会先执行solve函数。solve函数中有一个嵌套的for循环通过这个双层for循环我们可以遍历整个矩阵中的所有元素。嵌套for循环从第一行第一个元素也就是0,0开始发现这个位置是1于是island_num变成了1然后就会调用dfs(grid,0,0)此时solve函数被挂起等待dfs执行结束。进入dfs(grid, 0, 0)之后检查发现没有越界并且位置(0,0)的值为1接着将这个1改成0。再然后向四个方向继续蔓延处理掉所有连通的1。先来看dfs(0, 0)的向右分支也就是dfs(0, 1)发现值为1于是把它改成0然后继续蔓延。向左(0,0)发现是0刚才改的。向右(0,2)这里本来就是0。向上(-1, 1)越界直接返回。向下(1,1)本来就是0返回。dfs(0, 1)执行完成返回上一层。然后执行dfs(0, 0)的向下分支也就是dfs(1, 0)值为1改成0。它也会向四个方向蔓延但是由于它周围要不原本就是0要不就是被我们处理成了0因此它向四个方向的dfs都会直接返回。然后dfs(1, 0)执行完毕返回上一层。dfs(0, 0)的其他分支向上和向左都会越界直接return此时左上角的连通块(0,0), (0,1), (1,0)已经全都变成了0。然后dfs(0, 0)运行彻底结束程序接着刚才挂起的solve函数继续执行。接着进行for循环第一行第二个元素这个位置原本是1但是已经被我们改成0了于是直接跳过。中间所有的元素已经全为0全部跳过直到第三行第三个元素。发现是1island_num变成 2然后调用dfs(grid, 2, 2)重复上面的蔓延过程最终这个位置也变成了0。5. 代码优化假设修改一下代码对角线相连的 1 也算同一个岛屿即 8 个方向都能扩散。请思考一下怎么改代码其实很简单只用再加上四行对角线遍历的代码就行让从当前位置可以向左上左下右上右下蔓延。voiddfs(vectorvectorchargrid,intr,intc){intnrgrid.size();intncgrid[0].size();if(r0||rnr||c0||cnc||grid[r][c]0){return;}grid[r][c]0;dfs(grid,r,c-1);dfs(grid,r,c1);dfs(grid,r-1,c);dfs(grid,r1,c);//只需要添加下面四行即可dfs(grid,r-1,c-1);dfs(grid,r-1,c1);dfs(grid,r1,c-1);dfs(grid,r1,c1);}但是这段代码有 8 行dfs看起来有点难看于是我们还可以进行如下修改//8个方向的偏移量上下左右和4个对角线intdr[]{-1,1,0,0,-1,-1,1,1};intdc[]{0,0,-1,1,-1,1,-1,1};voiddfs(vectorvectorchargrid,intr,intc){//...越界检查...grid[r][c]0;//一个循环搞定所有方向for(inti0;i8;i){dfs(grid,rdr[i],cdc[i]);}}6. 岛屿问题变形这道题目可能还会出一些变形对于这些变形题只需要在上面代码中进行微调即可。6.1 求最大岛屿面积题目要求不再是数有多少个岛而是找出面积最大也就是包含 1 最多的那个岛。代码微调dfs函数不再返回void而是返回一个int代表这次处理掉了多少个 1。让dfs返回return 1 dfs(上) dfs(下) dfs(左) dfs(右)。solve函数中添加max_area max(max_area, dfs(r, c))。6.2 求岛屿周长题目要求计算岛屿边缘的长度。代码微调dfs 终止条件当你试图往海里走也就是grid 0或者越界时说明你撞到了边界。每撞到一次边界就return 1。最后把撞到的次数加起来6.3 封闭岛屿题目要求如果一个岛屿靠着地图边缘它就不算只数那些被海水完全包围的。代码微调写一个循环把地图四周边缘上的 1 全都作为起点跑一遍 dfs变成0。将得到的矩阵再用现在那套代码数剩下的岛屿。本文完。