
- 外文名
- BFS
- 别 称
- 广度优先搜索
- 应用学科
- 计算机
- 中文名
- 宽度优先搜索算法
- 适用领域范围
- 计算机算法
-
BFS
2018-12-07 23:44:12BFS//给一个地图由起点到点最短步数 .通*不通 //标准广搜模版题 #include<bits/stdc++.h> using namespace std; char mp[103][103]; //地图大小 int vis[103][103]; //访问标记 typedef struct point pt; //点重命名 struct point{int x;int y;}; //点结构体 typedef pair<pt,int> p; //pair存点与距离,方便队列 int dx[4]={0,0,-1,1}; //X偏移,上下左右 int dy[4]={1,-1,0,0}; //Y偏移,上下左右 int main(){ int n,m;cin>>n>>m; //地图大小 pt s,g; //定义起点与终点 for(int i=1;i<=n;i++){ //遍历行 for(int j=1;j<=m;j++){ //遍历列 cin>>mp[i][j]; //输入 if(mp[i][j]=='s'){ //如果是起点 s.x=i; //记下X s.y=j; //记下Y } if(mp[i][j]=='g'){//如果是终点 g.x=i; //记下X g.y=j; //记下Y } } } queue<p>qu; //开队列 qu.push(p(s,0)); //压入起点 while(!qu.empty()){ //非空 pt nowp=qu.front().first; //读出队首点 int dis=qu.front().second; //读出队首点到起点步数 vis[nowp.x][nowp.y]=1; //打上已访问标记 qu.pop(); //弹出队首 if(nowp.x==g.x&&nowp.y==g.y){cout<<dis<<endl;return 0;} //到终点跳出 for(int i=0;i<4;i++){ //未到终点则四个方向偏移 pt newp; //定义新点 newp.x=nowp.x+dx[i];if(newp.x<1 || newp.x>n)continue; //得新X,超限跳过 newp.y=nowp.y+dy[i];if(newp.y<1 || newp.y>m)continue; //得新Y,超限跳过 if(vis[newp.x][newp.y]==0&&mp[newp.x][newp.y]!='*'){ //未访问且可行 qu.push(p(newp,dis+1)); //新点压入队列 } } } cout<<"impossible"<<endl; //队空都走不到,就肯定走不到了 return 0; } /* in 3 3 s.. ... g.. out 2 in 3 3 s.. **. g.. out 6 in 3 3 s.. *** g.. out impossible */
-
bfs
2016-08-23 17:07:21bfs题意
给定一个有向无子环无重边的图,给定起点和终点,给定a,b,c三种路径长度,求最小次数ans,使得无论如何从a,b,c中选择ans次,均能在ans次之内走到终点
思路
1.预处理出某个点走a,b,c步后能否到达某个点
2.从终点bfs,倒着扩展能到达的其他点,因为若一个点走a,b,c步后均能到达必胜点则从该点出发也能达到终点,且步数为能到达的必胜点中最大的+1code
-
BFS_双端 BFS (BFS 求最短路)_电路维修
2020-02-18 14:30:08BFS在上一篇的基础上,发现 BFS 只能对与边权相同的图求最短路。实际上,在这篇要记录的题目中可以知道一张图中如果只有两种边权,那么最短路也是可以用 BFS 来求的,并且时间复杂度较低。
题目:
达达是来自异世界的魔女,她在漫无目的地四处漂流的时候,遇到了善良的少女翰翰,从而被收留在地球上。翰翰的家里有一辆飞行车。有一天飞行车的电路板突然出现了故障,导致无法启动。电路板的整体结构是一个 行 列的网格,如下图所示。
每个格点都是电线的接点,每个格子都包含一个电子元件。电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。在旋转之后,它就可以连接另一条对角线的两个接点。电路板左上角的接点接入直流电源,右下角的接点接入飞行车的发动装置。
达达发现因为某些元件的方向不小心发生了改变,电路板可能处于断路的状态。她准备通过计算,旋转最少数量的元件,使电源与发动装置通过若干条短缆相连。不过,电路的规模实在是太大了,达达并不擅长编程,希望你能够帮她解决这个问题。
注意:只能走斜向的线段,水平和竖直线段不能走。输入格式
输入文件包含多组测试数据。
第一行包含一个整数 ,表示测试数据的数目。
对于每组测试数据,第一行包含正整数 和 ,表示电路板的行数和列数。
之后R行,每行 个字符,字符是"/“和”"中的一个,表示标准件的方向。输出格式
对于每组测试数据,在单独的一行输出一个正整数,表示所需的缩小旋转次数。
如果无论怎样都不能使得电源和发动机之间连通,输出NO SOLUTION。数据范围
测评地址解法:把网格图的每个格点看成节点,当想从一个节点走到别的节点上时,如果原图中的线路允许则边权为0,如果需要旋转则为1。此时,再用 BFS 来求最短路,不过在搜索树上,边权为0的点应该在边权为1的点前被扩展,因此采取双端队列,若边权为0,则插入队头,否则插入队尾。
注意:
1、输入的“\”和“/”的处理要细心!
2、其实图中有一些节点是永远不可能走到的,因为走一步横纵坐标均变化1,因此必须与起点奇偶性相同才可以,这样也可以判断 NO SOLUTION 的情况。代码:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <deque> #define x first #define y second using namespace std; const int N=510; typedef pair<int ,int> pii; int T; int n,m; deque<pii> q; char g[N][N]; int dist[N][N]; bool v[N][N]; void bfs(){ q.push_back({0,0}); int dx[4]={-1,1,-1,1}; int dy[4]={-1,-1,1,1}; int ix[4]={-1,0,-1,0}; int iy[4]={-1,-1,0,0}; //*details!! char s[5]="\\//\\"; //det! memset(v,0,sizeof(v)); memset(dist,0x3f,sizeof(dist)); dist[0][0]=0; while(q.size()){ pii t=q.front(); //* q.pop_front(); //* //if(t.x==n && t.y==m) return ; if(v[t.x][t.y]) continue; v[t.x][t.y]=1; for(int i=0;i<4;i++){ int nx=t.x+dx[i],ny=t.y+dy[i]; if(nx<0 || nx>n || ny<0 || ny>m) continue; int gx=t.x+ix[i],gy=t.y+iy[i]; int w=(g[gx][gy]!=s[i]); int d=dist[t.x][t.y]+w; if(d<=dist[nx][ny]){ dist[nx][ny]=d; if(!w) q.push_front({nx,ny}); else q.push_back({nx,ny}); } } } } int main(){ cin>>T; while(T--){ cin>>n>>m; for(int i=0;i<n;i++) cin>>g[i]; bfs(); if((n+m)%2) cout<<"NO SOLUTION"<<endl; else cout<<dist[n][m]<<endl; } return 0; }
-
BFS_多源 BFS (用 BFS 求最短路)_矩阵距离
2020-02-18 14:07:10BFS上一篇搜索的博客讲了 BFS 一个经典的应用模型,这篇讲述另一个经典模型的一点小扩展。另一个 BFS 的经典应用模型是求一张具有相同边权的图上的单源点最短路,如果是多源点的最短路,实际上也是可以用 BFS 来解决的,
先看题目:给定一个 行 列的01矩阵 , 与 之间的曼哈顿距离定义为:
输出一个 行 列的整数矩阵 ,其中:
数据范围:
测试地址人话:求每一个0到离她最近的1的曼哈顿距离。
做法:将所有为零的点加入队列再进行 BFS 求最短路即可。
解释:BFS实际上就是最多在一颗搜索树的两层上扩展更新。而原先的单源点求最短路是以唯一的起点为根节点进行 BFS,在这道题里,我们可以不去管根节点是否只有一个,或者说加一个虚拟的超级根节点,她到每个0的边的权为0,然后再进行正常的 BFS 即可。代码:
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #define x first #define y second using namespace std; typedef pair<int,int> pii; const int N=1010; int g[N][N],n,m; pii q[N*N]; int d[N][N]; void bfs(){ int hh=0,tt=-1; memset(d,-1,sizeof(d)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(g[i][j]==1){ d[i][j]=0; q[++tt]={i,j}; } int dx[4]={0,1,0,-1}; int dy[4]={-1,0,1,0}; while(hh<=tt){ pii t=q[hh++]; for(int i=0;i<4;i++) { int nx=t.x+dx[i],ny=t.y+dy[i]; if(nx<=0 || nx>n || ny<=0 || ny>m) continue; if(d[nx][ny]!=-1) continue; d[nx][ny]=d[t.x][t.y]+1; q[++tt]={nx,ny}; } } } int main(){ cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%1d",&g[i][j]); bfs(); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) printf("%d ",d[i][j]); printf("\n"); } return 0; }
-
CBFS Connect CBFS Storage CBFS Disk CBFS Filter
2021-02-07 22:41:08CBFS连接--企鹅578867473索取Crack 在Windows应用程序中创建和管理虚拟文件系统。 CBFS筛选器 跟踪和控制文件系统,注册表以及流程管理器操作。 CBFS存储 在任何地方创建并嵌入安全的,功能齐全的文件系统。 ... -
广度优先搜索BFS bfs
2020-05-02 14:11:30广度优先搜索BFS bfs 广度优先搜索,又称宽度优先搜索,简称 bfs,我们以后都会用 bfs 来表示广度优先搜索。与深度优先搜索不同的是,广度优先搜索会先将与起始点距离较近的点搜索完毕,再继续搜索较远的点,而深搜...