t0ur1st

题目描述：

给定一个M行N列的迷宫图，其中 “0”表示可通路，”1″表示障碍物，无法通行。在迷宫中只允许在水平或上下四个方向的通路上行走，走过的位置不能重复走。
5行8列的迷宫如下：

0 1 1 1 0 0 0 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 0
0 1 1 1 0 1 1 0
1 0 0 0 0 0 0 0

则从左上角（1，1）至右下角（5，8）的最短路径为：
1,1–》2,1–》2,2–》2,3–》3,3–》3,4–》3,5–》4,5–》5,5–》5,6–》5,7–》5,8
题目保证每个迷宫最多只有一条最短路径。
请输出该条最短路径，如果不存在任何通路，则输出”NO FOUND”.

输入描述:

第一行，输入M和N值，表示迷宫行数和列数。
接着输入M行数值，其中，0表示通路，1表示障碍物。每列数值用空格符间隔。
接下来可能输入多组迷宫数据。
当输入M的值为-1时结束输入。

输出描述:

按行顺序输出路径的每个位置的行数和列数，如 x,y
如果不存在任何路径，则输出”NO FOUND”.
每组迷宫寻路结果用换行符间隔。

输入样例:

在这里给出一组迷宫。例如：
8 8
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 0
0 1 1 1 0 0 0 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 0
0 1 1 1 0 1 1 0
1 0 0 0 0 0 0 0
4 4
0 0 1 0
0 0 0 0
0 0 1 1
0 1 0 0
-1 -1

输出样例:

在这里给出相应的输出。例如：
1,1
2,1
3,1
4,1
5,1
5,2
5,3
6,3
6,4
6,5
7,5
8,5
8,6
8,7
8,8
NO FOUND

解题思路：

不想自定义结构体，那就先用pair<int,int>来表示一个坐标点吧。用G来表示迷宫地图，其中1为通 0为不通。用vis来判断迷宫地图中的坐标是否被访问过。用一个pair型的二维数组来记录(i,j)坐标的前一个坐标。先用一个queue来进行广度优先搜索 判断能否走到迷宫出口并记录所有能走通的坐标的前一个坐标。若迷宫能走通则从迷宫出口坐标点(m,n)开始，利用stack进行回溯，最后输出stack里面的坐标即可。若不能走通则输出NO FOUND。

AC代码：

#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)
#define ms(a,x) memset(a,x,sizeof(a))
#define P pair<int,int>     //P的first是坐标点的x,second是坐标点的y
#define mp(x,y) make_pair(x,y)
const int INF = 0x3f3f3f3f;   //无穷大
const int maxn = 505;
int G[maxn][maxn];      //迷宫地图,G[i][j]=1为通,0为不通
bool vis[maxn][maxn];   //判断vis[i][j]是否被访问过
P pre[maxn][maxn];    //pre[i][j]表示走到(i,j)的前一步
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int m,n;
    while(cin >> m >> n && m!=-1)
    {
        ms(G,-INF);
        ms(vis,false);
        Up(i,1,m)
        {
            Up(j,1,n)
            {
                cin >> G[i][j];
            }
        }
        queue<P> q;
        q.push(mp(1,1));
        bool found = false;   //能否找到迷宫出口
        while(!q.empty())
        {
            P cur = q.front();
            q.pop();
            int x = cur.first, y = cur.second;
            vis[x][y] = true;
            if(x==m && y==n)
            {
                found = true;
                break;
            }
            if(x>1 && !vis[x-1][y] && !G[x-1][y]) //若G[x-1][y]=1且该点未被访问过
            {
                q.push(mp(x-1,y));
                pre[x-1][y] = cur;
            }
            if(y>1 && !vis[x][y-1] && !G[x][y-1])
            {
                q.push(mp(x,y-1));
                pre[x][y-1] = cur;
            }
            if(x<m && !vis[x+1][y] && !G[x+1][y])
            {
                q.push(mp(x+1,y));
                pre[x+1][y] = cur;
            }
            if(y<n && !vis[x][y+1] && !G[x][y+1])
            {
                q.push(mp(x,y+1));
                pre[x][y+1] = cur;
            }
        }
        if(found)
        {
            stack<P> s;
            P cur(m,n);
            while(cur.first!=1 || cur.second!=1)    //从出口(m,n)开始回溯一直回溯到起点(1,1)为止
            {
                s.push(cur);
                cur = pre[cur.first][cur.second];
            }
            cout << 1 << "," << 1 << endl;
            while(!s.empty())
            {
                cout << s.top().first << "," << s.top().second << endl;
                s.pop();
            }
            cout << endl;
        }
        else cout << "NO FOUND" << endl;
    }
    return 0;
}