PTA7-1 迷宫寻路 (20分)

7-1 迷宫寻路 (20分)
给定一个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,8NO FOUND


程序思路：
（1）从入口元素开始，判断它上下左右的邻边元素是否满足条件，如果满足条件就入队列；
（2）取队首元素并出队列。寻找其相邻未被访问的元素，将其如队列并标记元素的前驱节点为队首元素；
（3）重复步骤（2），直到队列为空（没有找到可行路径）或者找到了终点。最后从终点开始，根据节点的前驱节点找出一条最短的可行路径。
程序实现：

#include<bits/stdc++.h>
using namespace std;
/**
* Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，
* 由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。
* 这里说下map内部数据的组织，map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，
* 所以在map内部所有的数据都是有序的，后边我们会见识到有序的好处。在一些特殊情况，比如关键字是一个结构体，涉及到排序就会出现问题，
* 因为它没有小于号操作，insert等函数在编译的时候过不去，既然是没有‘<’，那我们自己重载小于操作符应该就可以了。
*/
struct site{
int x,y,k;
friend bool operator<(const struct site& a, const struct site& b) {
if (a.x < b.x ||
(a.x == b.x && a.y < b.y)) {
return true;
}
return false;
}
}p[100];//将到终点的路线逆向保存
int main(){
int m, move[4][2] = { {1,0} , {0,1} , {-1,0} , {0,-1} };//用二维数组分别表示下右上左
cin>>m;
while(m != -1) {
map<site,site> f;//用来记录前驱
int n,a[100][100],flag = 1;
struct site temp;
queue<site> q;
cin>>n;
for(int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
cin>>a[i][j];
for(int i = 1; i <= m; i++) {//将周围用墙围起来
a[i][0] = 1;
a[i][n+1] = 1;
}
for (int j = 1; j <= n; j++){//将周围用墙围起来
a[0][j] = 1;
a[m+1][j] = 1;
}
temp.x = 1;
temp.y = 1;
q.push(temp);
a[1][1] = 6;//搜索过的地方值变为6
while(!q.empty()){
temp = q.front();//取队首坐标
q.pop();
int x = temp.x, y = temp.y;
if(x == m && y == n) {//如果找到终点
flag = 0;
int k = 0;
p[k++] = temp;
while(temp.x != 1 || temp.y != 1){//将到终点的路线逆向保存
p[k++] = f[temp];
temp = f[temp];
}
for(int i = k-1; i >= 0; i--)//输出路线
cout<<p[i].x<<','<<p[i].y<<endl;
break;
}
for (int w = 0; w < 4; w++) {//遍历四个方向
temp.x = x + move[w][0];
temp.y = y + move[w][1];
if(a[temp.x][temp.y] == 0){
q.push(temp);
a[temp.x][temp.y] = 6;//搜索过的地方值变为6
f[temp].x = x;
f[temp].y = y;
}
}
}
if(flag)
cout<<"NO FOUND";
cout<<endl;
cin>>m;
}
return 0;
}