C++:第十三讲BFS广度优先搜索

这篇具有很好参考价值的文章主要介绍了C++:第十三讲BFS广度优先搜索。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

今天带领大家学一下BFS。

DFS可以看——C++:第十二讲DFS深搜(二)_c++匿名函数dfs-CSDN博客

BFS简介

广度优先搜索(breadth-first search,缩写为bfs)又名宽度优先搜索,是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。BFS算法从问题的初始状态(起点)出发,根据状态转换规则(图结构中的边),遍历所有可能的状态(其他节点),直到找到终结状态(终点)。因此BFS算法的复杂度和状态集合的总数密切相关。首先访问初始顶点vi,并将其标记为已访问; 接着访问vi的所有未被访问过的邻接点vi1,vi2,…,vit,并均标记为已访问;(注意与DFS算法比较)

为什么要用到BFS呢?有的时候,对于DFS而言会陷入搜索过深仍然找不到解,也就意味着超时。因此,BFS就来了。尤其在连通性,最短路等问题。

例题1——洛谷P1605迷宫

链接——BFS(洛谷P1162)

题目描述

由数字 0 组成的方阵中,有一任意形状的由数字 1 构成的闭合圈。现要求把闭合圈内的所有空间都填写成 2。例如:6×6 的方阵(n=6),涂色前和涂色后的方阵如下:

如果从某个 0出发,只向上下左右 4 个方向移动且仅经过其他 0 的情况下,无法到达方阵的边界,就认为这个 0在闭合圈内。闭合圈不一定是环形的,可以是任意形状,但保证闭合圈内的 0 是连通的(两两之间可以相互到达)。

0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 1 0 1
1 1 1 1 1 1
0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 1 2 1
1 1 1 1 1 1

输入格式

每组测试数据第一行一个整数 n(1≤n≤30)。

接下来 n 行,由 0 和 1组成的 n×n 的方阵。

方阵内只有一个闭合圈,圈内至少有一个 0。

输出格式

已经填好数字 2的完整方阵。

输入输出样例

输入 #1

6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

输出 #1

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

说明/提示

对于 100% 的数据,1≤n≤30。

解题思路

首先,分析题目,这是要将闭合的“1”里面的“0”改写成“2”,然后输出。由此,我们猛然发觉,只要‘0’的联通块中,没有在边界,就是闭合的‘0’;(发现这个,就等于做对了一半;)因为,从正面推,找闭合中的‘0’不好找。所以,蒟蒻想到,运用BFS或者DFS直接搜索边界中‘0’,所在的联通块,然后标记。最后输出时,去除‘1’点和标记了的点,剩下的输出为‘2’,就是正解啦!!!

AC

#include <bits/stdc++.h>
using namespace std;
int N,A[55][55];
bool Flag[55][55];
int Dx[5]={0,-1,1,0,0};
int Dy[5]={0,0,0,-1,1};
void DFS(int i,int j){
	//越界 
	if(i<0||j<0||i>N+1||j>N+1) return ;
	//遍历过或者为1 
	if(Flag[i][j]==true||A[i][j]==1) return;
	Flag[i][j]=true; 
	for(int nx=1;nx<=4;nx++) DFS(i+Dx[nx],j+Dy[nx]);
	return ;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>N;
	//最外面的零层都是零(相当于在外面套一圈)
	//避免从左上角开始时是1 
	for(int i=1;i<=N;i++)
	 for(int j=1;j<=N;j++)
	    cin>>A[i][j]; 
	DFS(0,0);
	for(int i=1;i<=N;i++){	 
	  for(int j=1;j<=N;j++){
	 	//搜索不到的零 
	 	if(!A[i][j]&&Flag[i][j]==false) cout<<2<<" ";
		else cout<<A[i][j]<<" "; 
	  }
	  cout<<endl;	
	}

	return 0;
} 

 例题2——洛谷P1443马的遍历

链接——BFS(洛谷P1443)

题目描述

有一个 n×m 的棋盘,在某个点 (x,y) 上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

输入只有一行四个整数,分别为 n,m,x,y。

输出格式

一个n×m 的矩阵,代表马到达某个点最少要走几步(不能到达则输出 −1−1)。

输入输出样例

输入 #1

3 3 1 1

输出 #1

0    3    2   
3    -1   1   
2    1    4    

说明/提示

数据规模与约定

对于全部的测试点,保证 1≤x≤n≤400,1≤y≤m≤400。

解题思路

选择解决方案:

从一个点出发,搜寻另外的点,这明显是一道关于搜索的题目。至于用到深搜还是广搜,见下表:

C++:第十三讲BFS广度优先搜索,c++,宽度优先,开发语言,算法

从上图我们看到,BFS专门用于解决求两点之间最短路的问题,而DFS是用来解决求一个点到另一个点路径总数的问题。显然地,这题用到的是BFS。

注意事项:

“马走日,象走田”,在棋盘上,马按照“日”字的走法移动,对应到我们的数组大概是这样的:

(PS:其中红色为出发点,黄色为可到达的点)

我们发现,从[4][6]a[4][6]出发,可到达的点为:[2][5]a[2][5]、[3][4]a[3][4]、[2][7]a[2][7]、[3][8]a[3][8]、[5][4]a[5][4]、[6][5]a[6][5]、[6][7]a[6][7]、[5][8]a[5][8]。

AC

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y;
int hor[405][405];
bool vis[405][405];
int dx[]={1,2,-1,-2,-2,-1,1,2};
int dy[]={2,1,2,1,-1,-2,-2,-1};
void bfs(){
	queue<int> x1;
	queue<int> y1;
	//将马的初始位置放入队列中
	x1.push(x);
	y1.push(y);
	while(!x1.empty()){
		for(int i=0;i<8;i++){
			int xx=x1.front()+dx[i];
			int yy=y1.front()+dy[i];
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]){
				vis[xx][yy]=true;
				hor[xx][yy]=hor[x1.front()][y1.front()]+1;
				x1.push(xx);
				y1.push(yy);
			}	
		}
		x1.pop();
		y1.pop();
	}
}
int main(){
	cin>>n>>m>>x>>y;
	memset(hor,-1,sizeof(hor));
	hor[x][y]=0;
	vis[x][y]=true;
	bfs();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			printf("%-5d",hor[i][j]);
		}
		cout<<endl;
	}
}

课后练习(拓展难题)

链接——BFS(洛谷P1902)

题目描述

某组织正在策划一起对某大使的刺杀行动。他们来到了使馆,准备完成此次刺杀,要进入使馆首先必须通过使馆前的防御迷阵。

迷阵由 n×m 个相同的小房间组成,每个房间与相邻四个房间之间有门可通行。在第 n 行的 m 个房间里有 m 个机关,这些机关必须全部打开才可以进入大使馆。而第 11 行的 m 个房间有 m 扇向外打开的门,是迷阵的入口。除了第 11 行和第 n 行的房间外,每个房间都被使馆的安保人员安装了激光杀伤装置,将会对进入房间的人造成一定的伤害。第 i 行第 j 列 造成的伤害值为 pi,j​(第 11 行和第 n 行的 p 值全部为 00)。

现在某组织打算以最小伤害代价进入迷阵,打开全部机关,显然,他们可以选 择任意多的人从任意的门进入,但必须到达第 n 行的每个房间。一个士兵受到的伤害值为他到达某个机关的路径上所有房间的伤害值中的最大值,整个部队受到的伤害值为所有士兵的伤害值中的最大值。现在,这个恐怖组织掌握了迷阵的情况,他们需要提前知道怎么安排士兵的行进路线可以使得整个部队的伤害值最小。

输入格式

第一行有两个整数 n,m,表示迷阵的大小。

接下来 n 行,每行 m 个数,第 i 行第 j 列的数表示 pi,j​。

输出格式

输出一个数,表示最小伤害代价。

输入输出样例

输入 #1

4 2
0 0
3 5
2 4
0 0 

输出 #1

3

说明/提示

  • 50%的数据,n,m≤100;

  • 100%的数据,n,m≤1000,pi,j​≤1000。 

解题思路

题目概括出来,很容易想到二分。

求最大值最小,因此我们可以对最大伤害值进行二分。

如果某位置所受伤害值大于我们当前所限制的伤害值,我们肯定是不走这条路的.

AC

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
typedef long long ll;
typedef pair<ll,ll> pll;
int mod=1e9+7;
const int maxv=4e6+5;
ll n,m;
int a[1005][1005];
int get(int x,int y)//得到点的编号
{
	return (x-1)*m+y;
}
int p[maxv];
struct node
{
	int u,v,w;
}e[maxv];
int k;
int find(int x)
{
	if(p[x]!=x) return p[x]=find(p[x]);
	return p[x];
}
void solve()
{	
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			int c=get(i,j);
			p[c]=c;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int u=get(i,j);
			int v1=get(i+1,j);
			int v2=get(i,j+1);
			if(i+1<=n) e[k++]={u,v1,max(a[i][j],a[i+1][j])};
			if(j+1<=m) e[k++]={u,v2,max(a[i][j],a[i][j+1])};
		}
	}
	sort(e,e+k,[](node a,node b){
		return a.w<b.w;
	});
	int ans=0;
	int st=1,ed=n*m;
	for(int i=0;i<k;i++){
		int u=e[i].u,v=e[i].v,w=e[i].w;
		//cout<<u<<" "<<v<<" "<<w<<endl;
		int fu=find(u),fv=find(v);
		if(fu!=fv){
			p[fu]=fv;
			ans=max(ans,w);
		}
		if(find(st)==find(ed)) break;
	}
	cout<<ans<<endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t=1;
	while(t--){
		solve();
	}
	system("pause");
	return 0;
}

结尾

希望大家多多关注,下一个红包就在这!!!

本篇文章共5434字,如果你能支持一下我,我十分感谢!!!

如果有人想在洛谷上做题,可以点下方链接:

https://www.luogu.com.cn/

如果你喜欢或想了解一下其他的算法,可以看看以下这些:

题目详解系列(部分):

【万题详解】洛谷P1252 马拉松接力赛-CSDN博客

【万题详解】洛谷P1359 租用游艇-CSDN博客 

【百题详解】洛谷P8508 做不完的作业-CSDN博客

【万题详解1】洛谷P1230 智力大冲浪-CSDN博客

【全网首发】洛谷贪心题解集合-CSDN博客

洛谷二分题集(3题)-CSDN博客

游戏系列:

C++:史上最坑小游戏-CSDN博客

 C++:自创小游戏-CSDN博客

C++:下雪-CSDN博客

C++讲解系列(算法):

C++:第十二讲DFS深搜(二)_c++匿名函数dfs-CSDN博客

 C++:第十一讲DFS深搜-CSDN博客

C++:第十讲二分查找-CSDN博客

前缀和与差分:

C++:第九讲前缀和与差分-CSDN博客

贪心:

C++:第八讲贪心算法1-CSDN博客

C++讲解系列(基础入门):

排序:

C++:第七讲冒泡排序-CSDN博客

函数:

C++第6讲max和min函数_c++ min函数-CSDN博客

C++第五讲函数初步-CSDN博客

for循环&数组:

C++第四讲for循环及数组-CSDN博客

if语句&else语句及运算:

C++第三讲:C++中的逻辑运算符及if else语句-CSDN博客

基础:

C++第二讲输入与输出-CSDN博客

C++第一讲认识C++编译器-CSDN博客

欢迎收看,希望大家能三连!

最后认识一下,我是爱编程的喷火龙廖,我们有缘再见!文章来源地址https://www.toymoban.com/news/detail-822972.html

到了这里,关于C++:第十三讲BFS广度优先搜索的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 深度优先搜索(DFS)和广度优先搜索(BFS)

    代码随想录 深度优先搜索和广度优先搜索,都是图形搜索算法,它两相似,又却不同,在应用上也被用到不同的地方。这里拿一起讨论,方便比较。 先给大家说一下两者大概的区别: 如果搜索是以接近起始状态的程序依次扩展状态的,叫广度优先搜索。 如果扩展是首先扩展

    2024年02月02日
    浏览(56)
  • 广度优先搜索(BFS)

    注意:本内容主要是介绍用BFS实现图的遍历,所以需要对图的结构有所了解。 BFS(Breadth First Search,广度优先搜索,又名宽度优先搜索),与深度优先算法DFS往一个方向“死磕到底,不撞南墙不回头”的思维方式不同,广度优先搜索算法 关注的重点在于对每一层结点进行下一

    2023年04月09日
    浏览(41)
  • [BFS] 广度优先搜索

    常见的模板 // 使用一个数组判断元素是否入过队 int inqueue[N] = {0}; // 层数或者可以称为深度 int step = 0; // 判断是否可以入队的条件 int isvalid(){      } BFS(int x){     // 将初始的元素压入队列     // 注意每次压队的时候都要将inque[x] = 1,表明入队过     queueint q;     q.push(x);  

    2024年02月09日
    浏览(43)
  • 深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)

    目录 深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜) 深度优先搜索(简称“深搜”或DFS) 广度优先搜索 总结 深度优先生成树和广度优先生成树 非连通图的生成森林 深度优先生成森林 广度优先生成森林 图 1 无向图 深度优先搜索的过程类似于树 的先序遍历 ,首先

    2024年01月20日
    浏览(49)
  • 宽度优先搜索算法(BFS)

    宽度优先搜索算法(BFS) (也称为 广度优先搜索 )主要运用于树、图和矩阵(这三种可以都归类在图中),用于在图中从起始顶点开始 逐层 地向外探索,直到找到目标顶点为止。 在本篇文章中,我们主要讨论其在 树 中的运用 树的宽度优先搜索 即 树的层序遍历 :逐层访

    2024年03月12日
    浏览(49)
  • 深度优先搜索(DFS)和广度优先搜索(BFS),用代码讲原理

    以图文的形式对深度搜索和广度搜索的理论进行讲解时,可能会对一些概念有些模糊,且不太清楚怎么把该理论用程序的方式进行复现并解决这一搜索问题(这说的就是本人) 。所以后面我看完了一份实现这两种搜索方法的代码,在这做一个笔记,希望对大家有所帮助。 两

    2024年04月12日
    浏览(54)
  • Python 算法基础篇:深度优先搜索( DFS )和广度优先搜索( BFS )

    深度优先搜索( DFS )和广度优先搜索( BFS )是两种常用的图遍历算法,用于在图中搜索目标节点或遍历图的所有节点。本篇博客将介绍 DFS 和 BFS 算法的基本概念,并通过实例代码演示它们的应用。 😃😄 ❤️ ❤️ ❤️ 深度优先搜索( DFS )是一种用于遍历或搜索图或树

    2024年02月07日
    浏览(67)
  • 1432 - 走出迷宫的最少步数-广度优先搜索BFS

    代码

    2024年01月20日
    浏览(83)
  • 图的遍历——深度优先搜索(DFS)与广度优先搜索(BFS)(附带C语言源码)

    个人主页:【😊个人主页】 系列专栏:【❤️数据结构与算法】 学习名言:天子重英豪,文章教儿曹。万般皆下品,惟有读书高——《神童诗劝学》 第一章 ❤️ 学前知识 第二章 ❤️ 单向链表 第三章 ❤️ 递归 … 在此之前我们学习过了图的一些基本概念,如同在二叉树

    2024年02月06日
    浏览(69)
  • 图的遍历(搜索)算法(深度优先算法DFS和广度优先算法BFS)

    从图的某个顶点出发访问遍图中所有顶点,且每个顶点仅被访问一次。(连通图与非连通图) 1、访问指定的起始顶点; 2、若当前访问的顶点的邻接顶点有未被访问的,则任选一个访问之;反之,退回到最近访问过的顶点;直到与起始顶点相通的全部顶点都访问完毕; 3、若

    2024年01月17日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包