一.题目链接：

POJ-3984

二.题目大意：

给出一个迷宫，输出路径.

三.分析：

初学 bfs 的小伙伴在入坑 bfs 后，终于学会了判断迷宫问题是否能够到达终点。

那么， 现在又迎来了一个新的问题 —— 若迷宫的解唯一， 那么怎样输出迷宫路径呢 ？

比如 poj 3984 迷宫问题

在 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;
}