当前位置: 首页> 健康> 母婴 > 力扣-bfs

力扣-bfs

时间:2025/7/12 14:21:06来源:https://blog.csdn.net/weixin_63551790/article/details/140379103 浏览次数:0次

何为广度优先搜索?

广度优先搜索,即bfs。不同于dfs(走到底然后再换另外一条路),bfs更像是一层一层的走。

常常用来处理最短路径问题。

934.最短的桥

934. 最短的桥
题目

给你一个大小为 n x n 的二元矩阵 grid ,其中 1 表示陆地,0 表示水域。

 是由四面相连的 1 形成的一个最大组,即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。

你可以将任意数量的 0 变为 1 ,以使两座岛连接起来,变成 一座岛 。

返回必须翻转的 0 的最小数目。

示例 1:

输入:grid = [[0,1],[1,0]]
输出:1

示例 2:

输入:grid = [[0,1,0],[0,0,0],[0,0,1]]
输出:2

示例 3:

输入:grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
输出:1

提示:

  • n == grid.length == grid[i].length
  • 2 <= n <= 100
  • grid[i][j] 为 0 或 1
  • grid 中恰有两个岛
题解
前提条件为只有两座岛。要找到两座岛的最短距离。
标1为陆地,0为海洋。
那么我们可以先找到第一座岛,将1标为2.代表第一座岛。
这里可以使用dfs来进行寻找。
接着进行bfs,每一次都往四周走,然后进行判断,如果符合条件就把这个对应的ij压入队列进行判断。
class Solution {
public:const static inline vector<int> dirs={-1,0,1,0,-1};int shortestBridge(vector<vector<int>>& grid) {int m=grid.size(),n=grid[0].size();bool flag=false;queue<pair<int,int>> q;int i,j;for(i=0;i<m;i++){if(flag) break; for(j=0;j<n;j++){if(grid[i][j]==1){dfs(q,grid,m,n,i,j);flag=true;break;}}}int x,y;int level=0;while(!q.empty()){++level;int n1=q.size();while(n1--){auto [r,s]=q.front();q.pop();for(int k=0;k<4;k++){x=r+dirs[k],y=s+dirs[k+1];if(x>=0&&y>=0&&x<m&&y<n){if(grid[x][y]==2)continue;if(grid[x][y]==1)return level;q.push({x,y});grid[x][y]=2;}}}}return 0;}void dfs(queue<pair<int,int>>& q,vector<vector<int>>& grid,int m,int n,int i,int j){if(i<0||j<0||i==m||j==n||grid[i][j]==2)return ;if(grid[i][j]==0){q.push({i,j});return ;}grid[i][j]=2;dfs(q,grid,m,n,i+1,j);dfs(q,grid,m,n,i-1,j);dfs(q,grid,m,n,i,j-1);dfs(q,grid,m,n,i,j+1);}
};
关键字:力扣-bfs

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: