使用BFS解决城镇路径问题
有一个大小为n*m的矩形小镇，城镇上有房屋（“#”表示无法通过），有空地（“.”表示可通行），每次移动只能朝上下左右四个方向，且需花费1单位时间。
一天，二乔和承太郎约定在龙舌兰酒吧见面，两人同时从各自所在位置向酒吧出发。请问最少需要过多少时间他们才能在酒吧碰面。
地图上P表示二乔的位置，W表示承太郎的位置，B表示酒吧的位置。
输入格式:第一行包含两个整数n,m，表示城镇的大小。（1<=m,n<=1000)。
接下来n行，每行m个字符，表示小镇的情况。
输出格式:输出两人在酒吧碰面的最少花费时间，如果无法在酒吧碰面则输出-1。
输入样例:5 4
.W.#
P#..
....
B..#
#...
输出样例:4 代码:
#include<stdio.h>
#include<string.h>
char map[1002][1002];
int done[1002][1002];
int xx[4] = {-1, 0, 1, 0};
int yy[4] = {0, -1, 0, 1};
int n, m;
struct point
{
int x, y;
int step = 0;
};
int bfs(struct point start, struct point end)
{
memset(done, 0, sizeof(done));
struct point queue[10000]; int front = 0, rear = 1;
queue[0] = start;
while (rear != front)
{
if (queue[front].x == end.x && queue[front].y == end.y) return queue[front].step;
for (int i = 0; i < 4; i++)
{
int dx = queue[front].x + xx[i];
int dy = queue[front].y + yy[i];
if (dx >= 1 && dx <= m && dy >= 1 && dy <= n && done[dy][dx] == 0 && map[dy][dx] != '#')
{
done[dy][dx] = 1;
queue[rear].x = dx;
queue[rear].y = dy;
queue[rear++].step = queue[front].step + 1;
}
if (rear >= 10000) rear = 0;
}
if (++front >= 10000) front = 0;
}
return -1;
}
int main()
{
scanf("%d %d", &n, &m);
struct point W, P, B;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
scanf("%c", &map[i][j]);
if (map[i][j] == 10) scanf("%c", &map[i][j]);
switch (map[i][j])
{
case 'W':{W.x = j; W.y = i;} break;
case 'P':{P.x = j; P.y = i;} break;
case 'B':{B.x = j; B.y = i;} break;
}
}
int step_W = bfs(W, B), step_P = bfs(P, B);
if (step_W == -1 || step_P == -1) printf("-1");
else printf("%d", step_W < step_P ? step_P : step_W);
return 0;
}
总结:还是一道bfs的题。但是这道题很好想，就是找两个人分别到酒吧所需的步数再取大，有一个人到不了那就返回-1就行。
但是实际做题的过程里我还是遇到了不少的问题，这里总结几个值得（我自己）注意的点：
1.地图的读取，对这种字符类的要对换行符‘ n’ 特别关照一下。
2.步数标记数组的重置，像这个要多次bfs的题要注意每次找的时候标记用的数组一定要初始化！
3.函数里面数组别开太大，为了避免多写一行，我本来是在函数里面开的done[1002][1002]数组，但是发现这代码在自己电脑上会报错，但是放PTA上就AC，百思不得其解最后发现是这里的问题。
相关知识
小鼠迷宫问题
[国家集训队]部落战争
浅谈城镇居住区绿化规划设计中存在问题及改进措施.doc
关于《昆明市城镇绿化条例实施细则》的政策解读
腐烂的橘子BFS算法解析
PS 路径与文本工具的使用技巧（纯干货）
mysql数据库的乱码问题原因及解决
庙城镇“微改造”提升居民幸福感
一篇文章，解决椰糠五大使用问题！
森林城市建设的路径(精选5篇)
网址: 使用BFS解决城镇路径问题 https://m.huajiangbk.com/newsview1589712.html
| 上一篇: 龙舌兰酒吧为什么进不去 |
下一篇: 龙舌兰酒和威士忌的区别 龙舌兰酒 |
