应该是我博客的第一篇广度优先搜索的算法了吧，之前题目都用的DFS，因为DFS确实比较熟练点，BFS虽然很久之前就知道他是怎么实现的但是没怎么自己真正实践过~~~而且以前一听队列就头大，不过最近这方面需求还挺大的-.-
了解下BFS
宽度优先搜索
(Breadth First Search)
宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
简单的说应该就是，搜索当前可以到达的地方，压入队列，然后再取首元素，再查找，继续压入队列，与DFS有什么不同呢：把两个搜索比作探案，DFS就像是先摸着一个线索，然后深究到最后，如果不通再返回，查看有没有其他错过的东西，而BFS就像有逻辑的侦探，先找到能找到的所有线索，把它们收集起来，然后再一个个拨开，把它们后面的线索再收集起来。
在这里提供一个模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 迷宫题型
void bfs(){
起点入队
while(队列不为空){
当前点 = queue.front();
for(四个方向){
xx=x+上下左右
yy=y+上下左右
if(判断X，y有无越界){
continue;
}
if(如果能走){
结构体 k;
queue.push(k);
标记
}
}
}
}
|
推荐
正月点灯笼:BFS讲解
如果有时间的话可以看下上面这个博主的视频，很久以前关注的，这个真的讲的很形象~~
来道例题
题目
最近新冠病毒疫情非常严重，由于我们国家采取了有力的措施，才没有使疫情进一步的扩大。今天，作为计算机专业的学生，我们来用程序模拟一下各种情况下的新冠病毒传播情况。现在给定一个n * m的网格，每个网格可以有以下三个值之一：
值 0 代表隔离带。
值 1 代表健康人群。
值 2 代表感染人群。
每天，任何与感染人群（在 4 个正方向上）相邻的健康人都会感染。如果遇到隔离带，病毒就会被阻断。
输出直到单元格中没有健康人为止所必须经过的最小天数。如果不可能所有人都被感染，输出 -1。
输入
测试数据由多组测试样例组成。第一行输入两个正整数 n ( 1 <= n <= 500 ） 和 m ( 1 <= m <= 500 ），
接下来输入n * m个数字，数字均由 0 ， 1 ，2构成
输出
每组测试样例，输出直到单元格中没有健康人为止所必须经过的最小天数。如果不可能，输出 -1。
样例输入
1
2
3
4
5
6
7
8
9
10
| 3 3
2 1 1
1 1 0
0 1 1
3 3
2 1 1
0 1 1
1 0 1
1 2
0 2
|
样例输出
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include<bits/stdc++.h>
using namespace std;
int dir[4][2]={0,1,1,0,-1,0,0,-1};
int Map[1000][1000];
int qx;
int qy;
int n,m,sum;
struct fun{
int x;
int y;
int t;
}great;
queue<fun> q;
void bfs(){
while(q.size()){
fun num= q.front();
if(num.t>sum)
sum=num.t;
q.pop();
for(int i=0;i<4;i++){
int xx=num.x+dir[i][0];
int yy=num.y+dir[i][1];
if(xx<0||xx>n||yy<0||yy>m){
continue;
}
if(Map[xx][yy]!=0&&Map[xx][yy]!=2){
fun k;
k.x=xx;
k.y=yy;
k.t=num.t+1;
q.push(k);
Map[xx][yy]=2;
}
}
}
}
int main(){
while(scanf("%d %d",&n,&m)!=EOF){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
scanf("%d",&Map[i][j]);
if(Map[i][j]==2){
great.x=i;
great.y=j;
great.t=0;
q.push(great);
}
}
}
sum=0;
bfs();
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(Map[i][j]==1){
sum=-1;
}
}
}
printf("%d\n",sum);
}
return 0;
}
|