BFS常见模板题（初学BFS推荐，附例题由浅入深）

喜欢ヅ旅行 2023-07-12 14:14 114阅读 0赞

## BFS类题目：主要考查对广度搜索的理解。 ##

BFS相比于暴力枚举来说效率更高。  
BFS只要将范围矩阵扫一次即可得出答案。  
本文通过队列来实现求解，当然也可以用其他方式实现广度搜索。

#### First question：馋嘴羊 ####

![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]  
BFS思路（可能会比较抽象，建议结合代码理解）：  
第一步：输入矩阵、开始吃草位置  
第二步：判断开始吃草位置1有没有草  
如果有草  
第三步：将该位置1入队  
第四步：取队伍首元素为位置x  
第五步：判断位置x上、下、左、右的位置有没有草  
第六步：将有草的位置入队  
第七步：将位置x对应的inf置为true,ans++  
重复四~七步直到队伍中没有成员  
最后输出ans  
如果没草  
输出0

#include<bits/stdc++.h>
    #include<queue>
    using namespace std;
    int n, m, x, y, ans=0;
    const int maxn=1000;
    int matrix[maxn][maxn];
    bool inf[maxn][maxn]={ false};
    
    int X[4]={ 0, 0, -1, 1};
    int Y[4]={ -1, 1, 0, 0};
    
    struct node{ 
    	int x;
    	int y;
    }Node, top;
    
    bool judge(int xx, int yy)
    { 
    	if(xx<0||yy<0||xx>=n||yy>=m)
    	return false;
    	if(inf[xx][yy]==true||matrix[xx][yy]==0)
    	return false;
    	return true;
    }
    
    
    void BFS(int x, int y)
    { 
    	queue<node> q;
    	Node.x=x;
    	Node.y=y;
    	q.push(Node);
    	while(!q.empty())
    	{ 
    		top=q.front();
    		int nx=top.x;
    		int ny=top.y;
    		for(int i=0; i<4; i++)
    		{ 
    			if(judge(nx+X[i], ny+Y[i]))
    			{ 
    				Node.x=nx+X[i];
    				Node.y=ny+Y[i];
    				q.push(Node);
    			}
    		}
    		ans++;
    		inf[nx][ny]=true;
    		q.pop();
    	}
    }
    
    
    int main()
    { 
    	cin>>n>>m>>x>>y;
    	
    	for(int i=0; i<n; i++)
    	for(int j=0; j<m; j++)
    	cin>>matrix[i][j];
    	
    	if(matrix[x][y]==1)
    		BFS(x, y);
    	cout<<ans;
    	
    	return 0;
    }

#### Second question：走出迷宫 ####

给定一个nm大小的迷宫，其中 \* 代表不可通过的墙壁，而"."代表平地，S代表起点，T代表终点。移动过程中，如果当前位置是(x,y)(下标从0开始)，且每次只能前往上下左右(x,y+1),(x,y-1),(x-1,y)(x+1,y)四个位置的平地，求从起点S达到终点T的最少步数。

Sample Input:  
5 5 //5行5列  
… //迷宫信息  
.*.*.  
.*S*.  
.\*\**T  
…*  
2 2 3 4 //起点S的坐标和终点T的坐标

Sample Output:  
7  
上面样例中，S的坐标为(2,2) T的坐标为(4,3)  
注意：这道题与前面又略有不同，题目要求最少步数。  
我们可以通过改变结点node结构，加入setp变量，作为记录每个位置的最少步数，这也体现了结构的灵活性。

#include<bits/stdc++.h>
    #include<queue>
    using namespace std;
    
    struct node{ 
    	int x;
    	int y;
    	int step;
    }Node, top;
    
    const int maxn=1000;
    char matrix[maxn][maxn];
    bool inf[maxn][maxn]={ false};
    int X[4]={ 0,0,-1,1};
    int Y[4]={ -1,1,0,0};
    int n, m, ant;
    node a, S, T;
    
    bool judge(int xx, int yy)
    { 
    	if(xx<0||xx>=n||yy<0||yy>=m)
    	return false;
    	if(matrix[xx][yy]=='*'||inf[xx][yy]==true)
    	return false;
    	return true;
    }
    
    node BFS(int x, int y)
    { 
    	queue<node> q;
    	Node.x=x;
    	Node.y=y;
    	q.push(Node);
    	while(!q.empty())
    	{ 
    		top=q.front();
    		int nx=top.x;
    		int ny=top.y;
    		if(top.x==T.x&&top.y==T.y)//T.step只会被赋值一次，最先赋值路程最短 
    		return top;
    		for(int i=0; i<4; i++)
    		{ 
    			if(judge(nx+X[i], ny+Y[i]))
    			{ 
    				Node.x=nx+X[i];
    				Node.y=ny+Y[i];
    				Node.step=top.step+1;
    				q.push(Node);
    			}
    		}
    		inf[nx][ny]=true;
    		q.pop();
    	}
    }
    
    
    int main()
    { 
    	cin>>n>>m;
    	for(int i=0; i<n; i++)
    	{ 
    		getchar();
    		for(int j=0; j<m; j++)
    			matrix[i][j]=getchar();
    	}
    	cin>>S.x>>S.y>>T.x>>T.y;
    	S.step=T.step=0;
    	
    	a=BFS(S.x, S.y);
    	
    	cout<<a.step<<endl;
    	return 0;
    }

#### Third question：Fire Game ####

[题目链接][Link 1]  
大概题意：有一个棋盘的每个格子都是由草坪或者空地组成的。众所周知，假如草坪 (x,y) 着火，那么火会向草坪四周(x+1, y)、(x, y+1)、(x-1, y)、(x, y-1)蔓延。现在要点燃两块草坪开始，求最快多久点燃所有的草坪，第一次点燃草坪时间记为0，蔓延到下一块草坪记为1，以此类推。

误区：分情况讨论。  
正解：直接枚举可能选择的两块草坪，进行 bfs 维护一个最优解。  
注意点：选择的草坪可以为同一块草坪。

#include<iostream>
    #include<queue>
    #include<memory.h>
    using namespace std;
    int tj, ans, n, m, c_x[100], c_y[100];
    bool judge[15][15], tmp_judge[15][15];
    int X[4] = { 0, 0, -1, 1};
    int Y[4] = { 1, -1, 0, 0};
    
    struct node{ 
    	int x, y, step;
    }top;
    
    void bfs(int a_x, int a_y, int b_x, int b_y){ 
    	int tmp_ans=0, tmp_tj=0;
    	memcpy(tmp_judge, judge, sizeof(judge));
    	
    	queue <node> q;
    	q.push((node){ a_x, a_y, 0});
    	q.push((node){ b_x, b_y, 0});
    	tmp_judge[a_x][a_y]=false;
    	tmp_judge[b_x][b_y]=false;
    	
    	while(!q.empty()){ 
    		tmp_tj++;
    		top = q.front();
    		q.pop();
    		tmp_ans = top.step;
    		
    		int x=top.x, y=top.y;
    		for(int i=0; i<4; i++)
    		if(tmp_judge[x+X[i]][y+Y[i]]){ 
    			tmp_judge[x+X[i]][y+Y[i]]=false;
    			q.push((node){ x+X[i], y+Y[i], top.step+1});
    		}
    	}
    	//存在取同个草坪的情况：tj+1 == tmp_tj
    	if(tj <= tmp_tj)	
    		ans = min(tmp_ans, ans);
    		
    	return;
    }
    
    int main(){ 
    	int t;
    // freopen("data.txt","r", stdin);
    	scanf("%d", &t);
    	for(int k=1; k<=t; k++){ 
    		tj=0, ans=0x3f3f3f3f;
    		memset(judge, false, sizeof(judge));
    
    		scanf("%d %d", &n, &m);
    		for(int i=1; i<=n; i++)
    		for(int j=1; j<=m; j++){ 
    			char ch;
    			while(scanf("%c", &ch) && ch!='.' && ch!='#');
    			if(ch=='#'){ 
    				//标记草坪位置
    				judge[i][j] = true;	
    				//存储草坪位置信息
    				c_x[tj] = i;
    				c_y[tj] = j;
    				//统计所有草坪数
    				tj++;	
    			}
    		}
    		
    		//可以选择同一块草坪
    		for(int i=0; i<tj; i++)
    		for(int j=i; j<tj; j++)
    			bfs(c_x[i], c_y[i], c_x[j], c_y[j]);
    			
    		if(ans!=0x3f3f3f3f)
    			printf("Case %d: %d\n", k, ans);
    		else 
    			printf("Case %d: -1\n", k);
    	}
    	
    	return 0;
    }

#### Fourth question：Fire! ####

[题目链接][Link 2]  
题目大意：乔要逃离迷宫。已知乔在迷宫中的位置以及迷宫中哪些方格着火了，你必须确定乔是否能在火到达他之前走出迷宫，以及他能以多快的速度完成这一任务。  
乔和火每分钟移动一个正方形，垂直或水平移动(不是对角线)。  
火势从每个着火的广场向四面八方蔓延。乔可以从迷宫边缘的任何广场上走出迷宫。  
乔和火都不能进入被墙占据的广场。

输入：  
输入第一行输入包含一个整数，要遵循的测试用例数量。  
每个测试用例的第一行包含两个整数R和C，用空格分隔，1≤R，C≤1000。  
测试用例的以下R行包含迷宫的一行。  
每一行都包含准确的C字符，每个字符都是其中之一：  
\#，一个墙  
.，一个可通过的方格  
J，Joe在迷宫中的初始位置，也就是一个可通行的正方形F，一个正在燃烧的正方形。  
每个测试用例中都会有一个J。

输出：  
对于每个测试用例，输出一行“IMPOSSIBLE”，如果Joe不能在火到达之前离开迷宫，或者一个整数，给出Joe可以安全地在几分钟内安全离开迷宫的最早时间。

样例输入  
2  
4 4

####  ####

\#JF\#  
\#…\#  
\#…\#  
3 3  
\#F\#  
\#J.  
\#.F  
样例输出  
3  
IMPOSSIBLE

--------------------

解题思路：  
①、对有火的方块进行 bfs\_fire，利用 fire\_time 记录着火点着每一个方格的最快时间，利用 tmp\_fire 记录可能着火的方格。

void bfs_fire(){ 
    	memcpy(tmp_fire, v, sizeof(tmp_fire));
    	
    	while(!q_fire.empty()){ 
    		top = q_fire.front();
    		q_fire.pop();
    		for(int i=0; i<4; i++){ 
    			int dx = top.x+X[i];
    			int dy = top.y+Y[i];
    			if(judge(dx, dy, 1)){ 
    				tmp_fire[dx][dy] = false;
    				fire_time[dx][dy] = top.step+1;
    				q_fire.push((node){ dx,dy,top.step+1});
    			}
    		}
    	}
    }

②、对乔进行 bfs\_J，利用 J\_time 记录 J 可到达的方格在最快时间，利用 tmp\_J 记录可能到达的方格。并利用 fire\_time 求 J 最早离开迷宫时间。

void bfs_J(){ 
    	memcpy(tmp_J, v, sizeof(tmp_J));
    	
    	while(!q_J.empty()){ 
    		top = q_J.front();
    		q_J.pop();
    		
    		if(top.x==n||top.x==1||top.y==m||top.y==1){ 
    			if(J_time[top.x][top.y]<fire_time[top.x][top.y]||tmp_fire[top.x][top.y])
    				ans=min(ans, J_time[top.x][top.y]+1);
    		}
    		
    		for(int i=0; i<4; i++){ 
    			int dx = top.x+X[i];
    			int dy = top.y+Y[i];
    			if(judge(dx, dy, 2)){ 
    				tmp_J[dx][dy] = false;
    				J_time[dx][dy] = top.step+1;
    				q_J.push((node){ dx,dy,top.step+1});
    			}
    		}
    	}
    }

③、输出最早逃离时间。

--------------------

AC代码：

#include<iostream>
    #include<queue>
    #include<memory.h>
    using namespace std;
    int n, m, ans;
    int X[4] = { 0, 0, -1, 1};
    int Y[4] = { -1, 1, 0, 0};
    int fire_time[1010][1010], J_time[1010][1010];
    bool v[1010][1010], tmp_fire[1010][1010], tmp_J[1010][1010];
    
    struct node{ 
    	int x, y, step;
    }top;
    
    queue <node> q_fire;
    queue <node> q_J;
    
    bool judge(int x, int y, int num){ 
    	if(x>n||y>m||x<1||y<1)
    		return false;
    	if(num==1)
    		return tmp_fire[x][y];
    	if(num==2)
    		return tmp_J[x][y];
    }
    
    void bfs_fire(){ 
    	memcpy(tmp_fire, v, sizeof(tmp_fire));
    	
    	while(!q_fire.empty()){ 
    		top = q_fire.front();
    		q_fire.pop();
    		for(int i=0; i<4; i++){ 
    			int dx = top.x+X[i];
    			int dy = top.y+Y[i];
    			if(judge(dx, dy, 1)){ 
    				tmp_fire[dx][dy] = false;
    				fire_time[dx][dy] = top.step+1;
    				q_fire.push((node){ dx,dy,top.step+1});
    			}
    		}
    	}
    }
    
    void bfs_J(){ 
    	memcpy(tmp_J, v, sizeof(tmp_J));
    	
    	while(!q_J.empty()){ 
    		top = q_J.front();
    		q_J.pop();
    		
    		if(top.x==n||top.x==1||top.y==m||top.y==1){ 
    			if(J_time[top.x][top.y]<fire_time[top.x][top.y]||tmp_fire[top.x][top.y])
    				ans=min(ans, J_time[top.x][top.y]+1);
    		}
    		
    		for(int i=0; i<4; i++){ 
    			int dx = top.x+X[i];
    			int dy = top.y+Y[i];
    			if(judge(dx, dy, 2)){ 
    				tmp_J[dx][dy] = false;
    				J_time[dx][dy] = top.step+1;
    				q_J.push((node){ dx,dy,top.step+1});
    			}
    		}
    	}
    }
    
    int main(){ 
    	int t;
    	scanf("%d", &t);
    	while(t--){ 
    		ans = 0x3f3f3f3f;
    		scanf("%d%d", &n, &m);
    		
    		memset(fire_time, 0, sizeof(fire_time));
    		memset(J_time, 0, sizeof(J_time));
    		memset(v, false, sizeof(v));
    		
    		for(int i=1; i<=n; i++)
    		for(int j=1; j<=m; j++){ 
    			char ch;
    			while(scanf("%c", &ch)){ 
    				if(ch=='.'||ch=='#') break;
    				if(ch=='J'||ch=='F') break;
    			}
    			
    			if(ch=='.'||ch=='J')	 
    				v[i][j]=true;
    			if(ch=='J')				//起点 
    				q_J.push((node){ i, j, 0});
    			if(ch=='F')				//着火点 
    				q_fire.push((node){ i, j, 0});
    		}
    		bfs_fire();
    		bfs_J();
    		
    		if(ans!=0x3f3f3f3f)
    			printf("%d\n", ans);
    		else
    			printf("IMPOSSIBLE\n");
    	}
    	
    	return 0;
    }

希望能够将自己的一些学习经验分享给有需要的人。  
我是小郑，一个坚持不懈的小白。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200308215250117.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70
[Link 1]: http://acm.fzu.edu.cn/problem.php?pid=2150
[Link 2]: https://vjudge.net/problem/UVA-11624