【PTA】龙舌兰酒吧 （BFS求双源最短路）
目录
1.题目描述
2.输入输出
3.解题思路
4.样例解析
5.代码实现
1.题目描述
有一个大小为n*m的矩形小镇，城镇上有房屋（“#”表示无法通过），有空地（“.”表示可通行），每次移动只能朝上下左右四个方向，且需花费1单位时间。
一天，二乔和承太郎约定在龙舌兰酒吧见面，两人同时从各自所在位置向酒吧出发。请问最少需要过多少时间他们才能在酒吧碰面。
地图上P表示二乔的位置，W表示承太郎的位置，B表示酒吧的位置。
第一行包含两个整数n,m，表示城镇的大小。（1<=m,n<=1000)。
接下来n行，每行m个字符，表示小镇的情况。
输出两人在酒吧碰面的最少花费时间，如果无法在酒吧碰面则输出-1。
2.输入输出
输入样例:
5 4
. W . #
P # . .
. . . .
B . . #
# . . .输出样例:
4
3.解题思路
这道题就是典型的利用bfs（宽度优先搜索）来求解最短路的问题
如果两个人中有一个人无法到达目的地，则输出-1
如果两个人都能到达，则输出两个人到达时间后的最大值
4.样例解析
5.代码实现
定义 PII ，使用piar来储存坐标
C++ pair的基本用法总结（整理）_sevencheng798的博客-CSDN博客_c++ pair
使用结构体来存储出发点和终点的坐标（也可以使用pair来存储）
初始化结果为无穷大，以此来判断是否能到达终点
使用数组存储位移偏移量，方便下面直接使用循环来遍历地图（BFS）
cin >> n >> m; getchar(); for(int i = 1; i <= n; i ++ ) for(int j = 1; j > g[i][j]; if(g[i][j] == 'P') p1.x = i, p1.y = j; if(g[i][j] == 'W') w1.x = i, w1.y = j; if(g[i][j] == 'B') xp = i, yp = j; }注意这个 gecthcar() ，虽然本题并不会因为这个而过不了，但是我们出于严瑾的态度还是将最后的空格读掉 （cin 不会将最后的换行符读取）
然后先对先出发一个点，判断是否能到达，如果不能到达，直接输出 -1并return
这样的话属于是一种 剪枝 操作，能在一定程度上减少时间
时间对比：
当然，因为出发点是由我们人为选择的，所以也存在一定的偶然性
进入 BFS 操作：
首先初始一个 存储PII 的队列，并创建一个dist数组，初始化每个点为无穷大，用来存储每个点到出发点的距离
（如果是设置在全局变量，则需要重置数组为无穷大）
将出发点入队，并将出发点的距离置为0
核心代码（对列实现BFS）
当队列中还有元素时，将其取出并弹出队列
①如果这一点已经到达终点的时候，直接break 返回
②还未到达终点的时候
按照我们上面设置的位置偏移量数组 ，使用一个for循环遍历上下左右四个方向
将每个方向所到达的地址用变量临时存储并对其进行判断：
if(a > 0 && a 0 && b <= m && g[a][b] != '#' && dist[a][b] == INF)如果这个点在地图内部
a > 0 && a 0 && b <= m且这个点不是障碍物
&& g[a][b] != '#'且这个点之前没有遍历过（保证最短路性质）
&& dist[a][b] == INF则将这个点入队，并将其距离设置为前一个点的距离+1
{ q.push({a, b}); dist[a][b] = dist[t.first][t.second] + 1; }
同理对第二个出发点进行遍历和判断
cout << max(resp, resw) << endl;如果能够从上面走到走一步，证明两个出发点都能到达终点，则输出两者的最大值
AC代码
#include #include #include #include #define PII pair using namespace std;const int N = 1010, INF = 1e9;int n, m;int resp = INF, resw = INF;char g[N][N];struct Person{ int x, y;}p1, w1;int xp = 0, yp = 0;int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};int bfs(Person p){ queue q; int dist[N][N]; for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= m; j ++ ) dist[i][j] = INF; q.push({p.x, p.y}); dist[p.x][p.y] = 0; while(q.size()) { PII t = q.front(); q.pop(); if(t.first == xp && t.second == yp) break; for(int i = 0; i 0 && a 0 && b > n >> m; //getchar(); for(int i = 1; i <= n; i ++ ) for(int j = 1; j > g[i][j]; if(g[i][j] == 'P') p1.x = i, p1.y = j; if(g[i][j] == 'W') w1.x = i, w1.y = j; if(g[i][j] == 'B') xp = i, yp = j; } resp = bfs(p1); if(resp == INF) { cout << -1 << endl; return 0; } resw = bfs(w1); if(resw == INF) { cout << -1 << endl; return 0; } cout << max(resp, resw) << endl; return 0;}
