迷宫问题 （POJ - 3984 ，BFS + 路径输出）
一.题目链接：
POJ-3984
二.题目大意：
给出一个迷宫，输出路径.
三.分析：
初学 bfs 的小伙伴在入坑 bfs 后，终于学会了判断迷宫问题是否能够到达终点。
那么， 现在又迎来了一个新的问题 —— 若迷宫的解唯一， 那么怎样输出迷宫路径呢 ？
在 AC 之后， 写这篇博客不仅是为了供大家学习，斧正， 更是为了自身的总结， 吸取教训。
题目如下 ：
我也在网上找了一些大神的方法， 可惜自己太菜， 完全看不懂啊， 最终经过自己的胡蒙乱凑终于找出了方法， 并把题AC 了， 嘿嘿嘿 。
在这里先说一下本菜鸡的失败经历 ：（好丢人呀 (꒦_꒦) ）
① ： 一开始想用map建立起两个结构体的映射的， 把每个子节点的父节点存起来， 最后一级一级地往上找，再逆向出就可以了。
怎么杨， 这种想法是不是很棒。
可是敲完后发现一编译就会出现一些奇怪的东西，（吐血.jpg）
请教大神后才发现原来map是有序的，又因为结构无法比较大小，所以要想实现需要结构体重载， 可是本菜鸡不会（留下 了不学无术的眼泪 · · ·）。
那就继续问度娘呗， 发现了一种叫做 unordered_map 的神奇无序版map（奸笑），哈哈哈， 眼瞅着就要做出来了，
而又双叒叕被打脸了，不知为啥编译还是无法通过， 一切都是自己想象啊。
至此， 本菜鸡不得不放弃这种方法。
② ： 睡觉之前， 我又冥思奇想了一种错误解法。 如果在结构体中定义 int 型的prex， prey ， 在父节点 p 走到每个子点 t 时都使 t.prex = p.x; t.prey = p.y , 这样打印时一级一级地返回就可以了。 无奈电脑已经关机， 只能第二天再试。
醒来之后， 立马把那一坨代码敲了上去， 却发现只有前两个点的坐标是正确的， 后面点的坐标都与第二个点的坐标相同，至此， 本菜鸡居然还没有意识到自己究竟错在了那里。 我居然还傻不愣登 && 百思不得其解地 debug。 （真是佩自己的智商 o(╥﹏╥)o ）
之后才发现， 因为返回时写的是 p.x = p.prex; p.y = p.prey; 所以只改变了终点的坐标， 并没有返回父节点。
至此， 第二种方法正式宣布流产。（555）
Finally， 在我冥（胡）思（蒙）苦（乱）想（造）之后， 终于敲出了解法， 如下 ：
思维图化 ：
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define PI acos(-1.0)
#define ll long long int
using namespace std;
const int M = 10;
bool a[M][M], vis[M][M];/// a 用来标记是否可走， vis 标记是否走过
struct node
{
int x, y, time;
};
int Move[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};///上下左右四个方向
void bfs()
{
map<int, node>PRE[50];///建立起坐标与父节点的联系
stack<int> st[2];///一个存 y ，一个存 x 并反向输出路径
struct node p, t;
queue<node> q;
p.x = 0;
p.y = 0;
p.time = 0;
q.push(p);
vis[0][0] = 1;
while(!q.empty())
{
p = q.front();
q.pop();
if(p.x == 4 && p.y == 4)/// end up 终点
break;
for(int i = 0; i < 4; ++i)
{
t = p;
t.x += Move[i][0];
t.y += Move[i][1];
if(a[t.y][t.x] && !vis[t.y][t.x])///若此点可走且没有走过
{///使用数组 a 的优点便体现在这里， 省去了判断边界的步骤。
t.time++;
PRE[t.y][t.x] = p;///标记 t 的父节点
q.push(t);
vis[t.y][t.x] = 1;
}
}
}
int n = p.time + 1;
while(n--)
{
st[0].push(p.y);///存入坐标
st[1].push(p.x);
p = PRE[p.y][p.x];///返回父节点
}
n = st[0].size();
while(n--)
{
cout << '(' << st[0].top() << ", " << st[1].top() << ')' <<'\n';///利用栈的特性进行逆向打印
st[0].pop();///弹出首元素
st[1].pop();
}
}
int main()
{
memset(vis, 0, sizeof(vis));
memset(a, 0, sizeof(a));///必须要初始化， 原因看下面
int data;
for(int i = 0; i < 5; ++i)
{
for(int j = 0; j < 5; ++j)
{
scanf("%d", &data);
if(data == 0)
a[i][j] = 1;///若 data 为 0，则说明此点可走，标记该点为 1.
else
a[i][j] = 0;
}
}
bfs();
return 0;
}
查看14道真题和解析