首页 > 分享 > 最小步数求龙舌兰酒吧会合：二维路径搜索算法

最小步数求龙舌兰酒吧会合：二维路径搜索算法

花匠小妙招
2025-01-14 23:08

龙舌兰酒吧

题目

有一个大小为n*m的矩形小镇，城镇上有房屋（“#”表示无法通过），有空地（“.”表示可通行），每次移动只能朝上下左右四个方向，且需花费1单位时间。
一天，二乔和承太郎约定在龙舌兰酒吧见面，两人同时从各自所在位置向酒吧出发。请问最少需要过多少时间他们才能在酒吧碰面。
地图上P表示二乔的位置，W表示承太郎的位置，B表示酒吧的位置。
输入格式
第一行包含两个整数n,m，表示城镇的大小。（1<=m,n<=1000)。
接下来n行，每行m个字符，表示小镇的情况。
输出格式：
输出两人在酒吧碰面的最少花费时间，如果无法在酒吧碰面则输出-1。
输入样例

5 4 .W.# P#.. .... B..# #... 123456

输出样例

4 1

代码

#include <iostream> #include <queue> using namespace std; char a[1005][1005]; char b[1005][1005]; int n,m; struct people {int x,y,z; }p,w; int dir1[]={1,0,-1,0},dir2[]={0,1,0,-1}; queue <people> q; int bfs(people P) {int i,j;for(i=0;i<=n+1;i++){for(j=0;j<=m+1;j++){b[i][j]=a[i][j];}}people p1,p2;p1=P;q.push(p1);while(!q.empty()){p2=q.front();q.pop();if(a[p2.x][p2.y]=='B'){while(!q.empty()){q.pop();}return p2.z;}for(i=0;i<4;i++){if(b[p2.x+dir1[i]][p2.y+dir2[i]]!='#'){p1.x=p2.x+dir1[i];p1.y=p2.y+dir2[i];p1.z=p2.z+1;b[p2.x+dir1[i]][p2.y+dir2[i]]='#';q.push(p1);}}}return -1; } int main() {cin>>n>>m;int i,j;for(i=1;i<=n;i++){for(j=1;j<=m;j++){cin>>a[i][j];if(a[i][j]=='P'){p.x=i;p.y=j;p.z=0;}if(a[i][j]=='W'){w.x=i;w.y=j;w.z=0;}}}for(j=0;j<=m+1;j++){a[0][j]='#';a[n+1][j]='#';}for(i=0;i<=n+1;i++){a[i][0]='#';a[i][m+1]='#';}int t1,t2;t1=bfs(p);t2=bfs(w);if(t1==-1||t2==-1){cout<<-1;}else{if(t1>=t2){printf("%d",t1);}else printf("%d",t2);}return 0; }

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101

代码分析

struct people {int x,y,z; }p,w; 1234

结构体记录某一时刻的状态，x，y为位置（x,y）,z为花的时间
p，w用来记录二乔和承太郎的初始状态

for(i=1;i<=n;i++){for(j=1;j<=m;j++){cin>>a[i][j];if(a[i][j]=='P'){p.x=i;p.y=j;p.z=0;}if(a[i][j]=='W'){w.x=i;w.y=j;w.z=0;}}}

12345678910111213141516171819

用数组a储存题目所给的信息，并记录P，W所在的位置

for(j=0;j<=m+1;j++){a[0][j]='#';a[n+1][j]='#';}for(i=0;i<=n+1;i++){a[i][0]='#';a[i][m+1]='#';} 12345678910

用‘#’将地图围起来，防止越界，也避免后面判断漏了条件
新地图如下：

###### #.W.## #P#..# #....# #B..## ##...# ###### 1234567

进入bfs函数环节

for(i=0;i<=n+1;i++){for(j=0;j<=m+1;j++){b[i][j]=a[i][j];}} 1234567

因为会改变已经过位置的符号作为标记，复制数组a存储于数组b，对b进行修改避免影响原地图

people p1,p2;p1=P;q.push(p1); 123

记录起点位置，入队

int dir1[]={1,0,-1,0},dir2[]={0,1,0,-1}; 1

与奇怪的电梯不同，这道题的方向较多，若一一列举有些麻烦，所以用数组储存位移偏移量，方便用来遍历地图。以及思路与之前写的奇怪的电梯差不多，所以只注释不太一样的点

while(!q.empty()){p2=q.front();q.pop();if(a[p2.x][p2.y]=='B'){while(!q.empty())//保证下一次调用函数时队列为空{q.pop();}return p2.z;}for(i=0;i<4;i++){if(b[p2.x+dir1[i]][p2.y+dir2[i]]!='#')//利用数组遍历地图{p1.x=p2.x+dir1[i];p1.y=p2.y+dir2[i];p1.z=p2.z+1;b[p2.x+dir1[i]][p2.y+dir2[i]]='#';q.push(p1);}}}

123456789101112131415161718192021222324

return -1; 1

如果没有相遇就返回-1，便于判断

t1=bfs(p);t2=bfs(w);if(t1==-1||t2==-1){cout<<-1;}else{if(t1>=t2){printf("%d",t1);}else printf("%d",t2);} 1234567891011121314

最后就是判断t1，t2是否都存在，若都存在则取较大的时间为答案，否则输出-1