【BFS/DFS 解决 FloodFill 算法】岛屿数量

文章目录题目解析方向向量BFS广度优先搜索算法原理标记数组全局变量层序遍历代码实现DFS深度优先搜索算法原理全局变量dfs 函数函数头函数体代码实现题目链接200. 岛屿数量题目解析首先介绍一下什么是FloodFill算法FloodFill算法也称为洪水填充算法指的是在区域中找到性质相同的联通块注意这里的联通块指的是上下左右相邻斜线不能算做相邻。该算法可以使用深度优先搜索和广度优先搜索来解决。回到题目题目给我们一个由1陆地和0水组成的的二维字符网格grid我们需要计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。示例1题目给出的二维网格grid是11110110101100000000那么岛屿只有一块11110110101100000000示例2题目给出的二维网格 grid11000110000010000011则有三块岛屿11000110000010000011方向向量在继续之前有必要知道我们在解决矩阵搜索类问题时访问某位置上下左右四个方向的操作。坐标〖i, j〗的上下左右四个坐标是在i和j加上了 0、1、-1 上下坐标〖i (-1), j 0〗和〖i 1, j 0〗左右坐标〖i 0, j (-1)〗和〖i 0, j 1〗。因此需要定义两个向量坐标dx {0, 0, -1, 1}dy {-1, 1, 0, 0}。在需要访问时通过 〖row, col〗坐标和四次循环依次访问即可。BFS广度优先搜索算法原理题目的本质是在二维矩阵中搜索因此我们可以遍历整个矩阵当找到一个未被标记的岛屿就更新岛屿数量记录并标记为已访问然后根据该岛屿的位置坐标通过层序遍历依次找到与其相连的所有未被标记过的陆地并标记为已访问当矩阵遍历完毕后返回统计到的岛屿数量标记数组我们在进行 BFS 的时候可能会重复进入某个方格。可以用两种方式避免重复访问在原数组上修改使用标记数组对于第一种方式在面试时需要确定能否在原数组上修改而第二种方式则更安全我们使用一个布尔类型的二维数组visit设置其大小与题目所给矩阵大小一样通过坐标能够对应矩阵中某个方格从而标记方格的访问状态。全局变量我们需要用到矩阵的行数和列数因此将m和n作为全局变量布尔类型的标记数组visit用于标记矩阵中某个方格是否已被访问方向数组dx和dy辅助我们从某个位置向其上下左右四个方向访问。intm,n;boolean[][]visit;int[]dx{0,0,-1,1};int[]dy{-1,1,0,0};层序遍历我们使用一个队列实现层序遍历的操作队列存储与〖row, col〗位置相连的陆地的坐标当队列不为空时一直取出队首元素获取坐标然后根据坐标向该元素的上下左右四个方向访问查找符合条件的陆地与该位置相连且未被访问过找到符合条件的陆地之后入队然后更新标记为已访问防止被重复访问当队列为空层序遍历完毕由于我们每次遍历矩阵找到一个未被标记过的岛屿时都要进行依次层序遍历操作因此将该操作封装为一个方法。代码实现classSolution{intm,n;// 矩阵grid的行数和列数boolean[][]visit;// 用于标记是否已访问// 辅助访问某一位置上下左右方向的数组int[]dx{0,0,-1,1};int[]dy{-1,1,0,0};publicintnumIslands(char[][]grid){intret0;// 用于统计岛屿的数量// 初始化mgrid.length;ngrid[0].length;visitnewboolean[m][n];// 遍历矩阵for(inti0;im;i){for(intj0;jn;j){if(grid[i][j]1!visit[i][j]){// 找到一块未被标记的岛屿ret;// 更新岛屿数量visit[i][j]true;// 将[i,j]位置做已访问标记bfs(grid,i,j);// 将与该岛屿相连的所有陆地通过BFS标记}}}// 返回统计的岛屿数量returnret;}publicvoidbfs(char[][]grid,introw,intcol){// 使用队列存储与[row,col]位置相连的坐标Queueint[]queuenewArrayDeque();queue.offer(newint[]{row,col});// 层序遍历while(!queue.isEmpty()){int[]topqueue.poll();// 取出队首元素rowtop[0];coltop[1];// 获取队首元素的坐标// 从队首元素向上下左右四个方向访问未被标记的陆地for(intk0;k4;k){intxrowdx[k],ycoldy[k];if(x0xmy0yn){if(grid[x][y]1!visit[x][y]){queue.offer(newint[]{x,y});// 符合条件,入队visit[x][y]true;// 标记该陆地为已访问}}}}}}DFS深度优先搜索算法原理遍历矩阵当找到一个未被标记过的岛屿时就更新岛屿的数量并标记然后从这个位置开始向四周深度优先搜索相邻的未被标记过的陆地直到搜索不到陆地为止。当矩阵遍历完毕返回所记录的岛屿的数量即可全局变量为了 dfs 函数递归方便将矩阵grid改成全局变量m和n记录矩阵的大小ret用于记录岛屿的数量。布尔类型的数组visit则用于标记已经发现的岛屿和陆地防止重复计入dx和dy方向数组用于访问指定位置的上下左右四个方向。char[][]grid;intm,n,ret;boolean[][]visit;int[]dx{0,0,-1,1};int[]dy{-1,1,0,0};dfs 函数函数头dfs 函数的任务是从指定位置出发访问它的四个方向因此函数的参数是row和col表示某位置的坐标。dfs(introw,intcol);函数体我们在 dfs 函数体中要做的事情就是从指定位置坐标[ row, col ]出发逐一访问该位置的上、下、左、右四个方向的位置看看是否是未记录过的陆地如果是就继续递归深搜否则不进行深搜。具体就是循环四次然后计算出下一个位置的坐标判断坐标是否合法若合法就进一步判断该坐标在 grid 矩阵中的值是否是 ‘1’ —— 该位置是陆地该坐标的在 visit 中的值是否不等于 “true” —— 该位置未被标记过若以上两个条件都满足就继续递归深搜。代码实现classSolution{char[][]grid;intm,n,ret;boolean[][]visit;int[]dx{0,0,-1,1};int[]dy{-1,1,0,0};publicintnumIslands(char[][]givenGrid){gridgivenGrid;mgrid.length;ngrid[0].length;visitnewboolean[m][n];for(inti0;im;i){for(intj0;jn;j){if(grid[i][j]1!visit[i][j]){// 找到未被标记过的岛屿标记该岛屿并更新岛屿数量visit[i][j]true;ret;dfs(i,j);// 从该位置开始向四周寻找相邻的陆地}}}returnret;}privatevoiddfs(introw,intcol){for(intk0;k4;k){intxrowdx[k],ycoldy[k];if(x0xmy0yn){if(grid[x][y]1!visit[x][y]){// 找到未被标记过的相邻陆地visit[x][y]true;dfs(x,y);}}}}}文章到这里就告一段落了若有错误请尽管指出完