Life has its own fate, and meeting may not be accidental.

0%

BFS宽度优先搜索(新冠病毒的传播)

应该是我博客的第一篇广度优先搜索的算法了吧,之前题目都用的DFS,因为DFS确实比较熟练点,BFS虽然很久之前就知道他是怎么实现的但是没怎么自己真正实践过~而且以前一听队列就头大,不过最近这方面需求还挺大的-.-

了解下BFS

宽度优先搜索
(Breadth First Search)

宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。

简单的说应该就是,搜索当前可以到达的地方,压入队列,然后再取首元素,再查找,继续压入队列,与DFS有什么不同呢:把两个搜索比作探案,DFS就像是先摸着一个线索,然后深究到最后,如果不通再返回,查看有没有其他错过的东西,而BFS就像有逻辑的侦探,先找到能找到的所有线索,把它们收集起来,然后再一个个拨开,把它们后面的线索再收集起来。

在这里提供一个模板

1
迷宫题型
2
void bfs(){
3
    起点入队    //迷宫题用结构体存X,Y
4
    while(队列不为空){
5
        当前点 = queue.front();             //取出队首元素
6
        for(四个方向){
7
            xx=x+上下左右
8
            yy=y+上下左右
9
            if(判断X,y有无越界){
10
                continue;
11
            }
12
            if(如果能走){
13
                结构体 k;
14
                queue.push(k);
15
                标记
16
            }
17
        }
18
    }
19
}

推荐

正月点灯笼:BFS讲解
如果有时间的话可以看下上面这个博主的视频,很久以前关注的,这个真的讲的很形象~~


来道例题

题目

最近新冠病毒疫情非常严重,由于我们国家采取了有力的措施,才没有使疫情进一步的扩大。今天,作为计算机专业的学生,我们来用程序模拟一下各种情况下的新冠病毒传播情况。现在给定一个n * m的网格,每个网格可以有以下三个值之一:
值 0 代表隔离带。
值 1 代表健康人群。
值 2 代表感染人群。
每天,任何与感染人群(在 4 个正方向上)相邻的健康人都会感染。如果遇到隔离带,病毒就会被阻断。
输出直到单元格中没有健康人为止所必须经过的最小天数。如果不可能所有人都被感染,输出 -1。

输入

测试数据由多组测试样例组成。第一行输入两个正整数 n ( 1 <= n <= 500 ) 和 m ( 1 <= m <= 500 ),
接下来输入n * m个数字,数字均由 0 , 1 ,2构成

输出

每组测试样例,输出直到单元格中没有健康人为止所必须经过的最小天数。如果不可能,输出 -1。

样例输入

1
3 3
2
2 1 1
3
1 1 0
4
0 1 1
5
3 3
6
2 1 1
7
0 1 1
8
1 0 1
9
1 2
10
0 2

样例输出

1
4
2
-1
3
0

代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
int dir[4][2]={0,1,1,0,-1,0,0,-1};
4
int Map[1000][1000];
5
int qx;
6
int qy;
7
int n,m,sum;
8
struct fun{
9
	int x;
10
	int y;
11
	int t;
12
}great;
13
queue<fun> q;
14
void bfs(){
15
	while(q.size()){
16
		fun num= q.front();	//取出
17
		if(num.t>sum)
18
			sum=num.t;
19
		q.pop();
20
		for(int i=0;i<4;i++){
21
			int xx=num.x+dir[i][0];
22
			int yy=num.y+dir[i][1];
23
			if(xx<0||xx>n||yy<0||yy>m){	//越界 
24
				continue;
25
			}
26
			if(Map[xx][yy]!=0&&Map[xx][yy]!=2){	 
27
				fun k;
28
				k.x=xx;
29
				k.y=yy;
30
				k.t=num.t+1;
31
				q.push(k);
32
				Map[xx][yy]=2;
33
			}
34
		}
35
	}
36
}
37
int main(){
38
	while(scanf("%d %d",&n,&m)!=EOF){
39
		for(int i=0;i<n;i++){
40
			for(int j=0;j<m;j++){
41
				scanf("%d",&Map[i][j]);
42
				if(Map[i][j]==2){
43
					great.x=i;		//当前坐标 
44
					great.y=j;
45
					great.t=0;
46
					q.push(great);		//起始点压入 
47
				}
48
			}
49
		}
50
		sum=0;
51
		bfs();
52
		for(int i=0;i<n;i++){
53
			for(int j=0;j<m;j++){
54
				if(Map[i][j]==1){
55
					sum=-1;
56
				}
57
			}
58
		}
59
		printf("%d\n",sum);
60
	}
61
	return 0;
62
}