POJ-3984.迷宫问题(BFS + 路径输出)

时间:2022-01-21 18:41:52

昨天中午做的这道题,结果蛙了一整天,就因为一行代码困住了,今天算是见识到自己有多菜了。流泪.jpg

  本题大意:给一个5 * 5的迷宫,1表示墙壁,0表示通路,从左上角走到右下角并输出路径。

  本题思路:主要就是BFS寻路,为了方便打印,从右下角开始进行BFS。

  注意输出时候的大坑,会有标记。

  本题代码:

 #include <cstdio>
#include <queue>
#include <map>
using namespace std; typedef pair<int ,int > P;
const int n = , INF = 1e7;
int maze[n][n], d[n][n], dx[] = {, , -, }, dy[] = {, , , -};
P path[n][n];//用来保存每个结点的父节点,方便输出 void bfs() {
queue <P> s;
s.push(P(, ));//从终点到起点方便路径打印
for(int i = ; i < n; i ++)
for(int j = ; j < n; j ++) {
d[i][j] = INF;
path[i][j] = P(-, -);
}
d[][] = ;
while(s.size()) {
P p = s.front();
if(p.first == && p.second == ) break;
s.pop();
for(int i = ; i < ; i ++) {
int nx = p.first + dx[i], ny = p.second + dy[i];
if(nx >= && nx < n && ny >= && ny < n && maze[nx][ny] == && d[nx][ny] == INF) {
s.push(P(nx, ny));
d[nx][ny] = d[p.first][p.second] + ;
path[nx][ny] = P(p.first, p.second);
}
}
}
} int main () {
for(int i = ; i < n; i ++)
for(int j = ; j < n; j ++)
scanf("%d", &maze[i][j]);
bfs();
P p = make_pair(, );
while(p.first != -) {
printf("(%d, %d)\n", p.first, p.second);
int tmp = p.first;//这个很坑,坑了我4个小时,修改值之前进行记录
p.first = path[p.first][p.second].first;
p.second = path[tmp][p.second].second;
}
return ;
}