脚本宝典收集整理的这篇文章主要介绍了dfs和bfs解决岛屿问题,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
今天在力扣上学习算法,发现一道关于DFS和BFS的练习题,是一种比较基础,可以很好理解和运用这两种算法的题目。
以下是自己学习时借鉴他人的过程。
题目:岛屿数量
给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
示例:
输入:grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"]]输出:1
这个题目我的理解是:分为两部分,一部分是所处连续的1组成的完整岛屿,另一部分是单独的一个1也是一个岛屿。最重要的就是用代码区分这两类岛屿。
该题若想判断是连续岛屿还是单个岛屿,则需要判断每个岛屿的附近及上下左右是否有其他的岛屿,如果周围都没有则为单个岛屿。
我本人认为最容易理解的就是DFS算法。DFS算法就是类似于从起点到终点有很多个分岔路口,也就意味着有很多条路。你需要找一条路走到头,如果路不通则回到上一个分岔路口选择其他的路。
首先从第一个出发,若为1,将值变为0,记录总岛屿的变量+1,后使用dfs判断它的周围是否含有岛屿,按照上下左右顺序进行遍历,若上边为1,则判断上边的上下左右,就这样依次判断,直至退出这次dfs迭代,在这个过程当中,总岛屿的数量只加一次。
代码如下:
public class DAOYu { public int numIslands(char[][] grid){ if(grid==null || grid.length==0){ return 0; } int num=0; for(int i=0;i<grid.length;i++){ for(int j=0;j<grid[0].length;j++){ //只有当前格子是1 才开始计算 if(grid[i][j]=='1'){ num++;// 然后通过dfs把当前格子的上下左右四个位置为一的都要置为0// 因为连着一起的算一个岛屿 dfs(grid,i,j); } } } return num; } public void dfs(char[][] grid,int i,int j){ /*边界条件判断,不能越界*/ if(i<0 || i>=grid.length || j<0 || j>grid.length || grid[i][j]=='0'){ return; } grid[i][j]='0'; dfs(grid,i-1,j); dfs(grid,i+1,j); dfs(grid,i,j-1); dfs(grid,i,j+1); }BFS代码如下:
public static void bfs(char[][] grid,int x,int y){ grid[x][y]='0'; int n=grid.length; int m=grid[0].length; /*使用队列,存储的是格子坐标划的值*/ Queue<Integer> queue=new LinkedList<>(); int code=x*m+y; queue.add(code); while(!queue.iSEMpty()){ code=queue.poll();//出队 int i=code/m; int j=code%m; if(i>0 && grid[i-1][j]=='1'){//上 /*如果上面格子为1 置为0,然后加入到队列中*/ grid[i-1][j]='0'; queue.add((i-1)*m+j); } if(i<n-1 && grid[i+1][j]=='1'){//下 grid[i+1][j]='0'; queue.add((i+1)*m+j); } if(j>0 && grid[i][j-1]=='1'){//左 grid[i][j-1]='0'; } if(j<m-1 && grid[i][j+1]=='1'){ grid[i][j+1]='0'; } }}
以上是脚本宝典为你收集整理的dfs和bfs解决岛屿问题全部内容,希望文章能够帮你解决dfs和bfs解决岛屿问题所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。