优选算法_岛屿数量_floodfill算法)_bfs_C++

张开发
• 2026/4/21 22:33:17 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

优选算法_岛屿数量_floodfill算法)_bfs_C++
一.题目解析遍历整个二维数组,看有多少单独的连通域算法解析:floodfill算法1.遍历整个数组,遇到一个单独的连通域就使用bfs并且标记已经遍历的位置2.bfs时是遍历上下左右,遍历时没有改变性质就会重复遍历死循环比较考验代码能力,就是bfs时要做什么(边遍历边改true)等,结合代码给出注释.二.代码编写:class Solution { int dx[4]{0,0,-1,1}; int dy[4]{1,-1,0,0}; int vis[301][301]; int m,n; public: int numIslands(vectorvectorchar grid) { mgrid.size(),ngrid[0].size();//边界长度,采用的是全局变量 memset(vis,false,sizeof(vis));//初始化判断数组为false int ret0;//记录岛屿数量 for(int i0;im;i)//遍历整个数组 { for(int j0;jn;j) { if(grid[i][j]1!vis[i][j])//遇到一个未遍历的岛屿,采用bfs看看岛屿多大,并标记为true已遍历 { ret;//计数 bfs(grid,i,j);//bfs } } } return ret; } void bfs(vectorvectorchar grid,int i,int j) { queuepairint,intq;//队列来实现宽度优先遍历 q.push({i,j});//岛屿的第一个坐标入队 vis[i][j]true;//标记已遍历 while(!q.empty())//这个岛屿的其他坐标入队 { auto [a,b]q.front(); q.pop(); for(int k0;k4;k)//遍历四个方向 { int xadx[k],ybdy[k];//四个方向 if(x0xm y0yn grid[x][y]1!vis[x][y]) //四个方向都不能越界,并且要没有遍历过,符合已知性质 { q.push({x,y});//符合入队 vis[x][y]true;//标记已遍历 } } } } };我们创建的是反向数组,通过迭代就可以实现遍历四个方向.

更多文章