PTA7-1 迷宫寻路 (20分)

灰太狼 2023-07-24 02:27 27阅读 0赞

**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,8
    
    NO 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;
    }