week2 A - Maze

本文主要是介绍week2 A - Maze，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述：

东东有一张地图，想通过地图找到妹纸。地图显示，0表示可以走，1表示不可以走，左上角是入口，右下角是妹纸，这两个位置保证为0。既然已经知道了地图，那么东东找到妹纸就不难了，请你编一个程序，写出东东找到妹纸的最短路线。

Input:
输入是一个5 × 5的二维数组，仅由0、1两数字组成，表示法阵地图。
Output:
输出若干行，表示从左上角到右下角的最短路径依次经过的坐标，格式如样例所示。数据保证有唯一解。
Hint:
坐标(x, y)表示第x行第y列，行、列的编号从0开始，且以左上角为原点。
另外注意，输出中分隔坐标的逗号后面应当有一个空格。

解题思路：

此为迷宫地图问题，要找一条从起点到终点的路径，有两类解决方式，一类是使用队列结构对图进行广度优先搜索（BFS），另一类是使用栈结构对图进行深度优先搜索（DFS），但是此题要求找出最短序列，则应采用第一类方法。
BFS 引例 —— 迷宫问题：
数据结构：
坐标结构体Coordinate，Coordinate类型二位数组route——用来记录[i][j]位置的前一位置，即可生成路线。
bool类型数组maze——标记地图的障碍物。
x，y坐标偏移量数组dx，dy，用来遍历上下左右四个位置。

初始化地图后（数组最外一圈要全部放置障碍物）， 类似树的按层遍历。

1. 访问初始点(sx,sy)，并将其标记为已访问过（即在该点放置障碍物)，置前一位置为（-1，-1）。
2. 访问(sx,sy)的所有未被访问过可到达的邻接点，并均标记为已访问过，并置前一位置为（sx,sy)，将这些点加入到队列中。
3. 再按照队列中的次序，访问每一个顶点(sx,sy)的所有未被访问过的邻接点，
   并均标记为已访问过，加入到队列中，依此类推。
4. 直到到达终点或者图中所有和初始点Vi有路径相通的顶点都被访问过为
   止。

输出路径模块：起点到达终点的这条路径，每一个位置都记录了前一位置，故须逆向输出，此处借用坐标Coordinate类型的栈结构保存路径，首先终点入栈，借用循环结构，当前一位置的横坐标不为-1时，将前一位置保存在栈中。循环结束，依次从栈中弹出坐标，按格式输出，输出时横纵坐标一定要都减一！因为起点是（0，0)。

实验代码：

#include<iostream>
#include<queue>
#include<stack>
using namespace std;
struct coordinate 
{int x;int y;	coordinate(int x1,int y1){x=x1;y=y1;}coordinate(){x=-1;y=-1;}
}; bool maze[7][7];
coordinate route[7][7];		//存储每个点的前一个点 
int dx[]={0,1,0,-1};		//上右下左 
int dy[]={1,0,-1,0};bool searchroute(int x1,int y1,int x2,int y2)			//起点到终点 
{queue<coordinate> q;coordinate coor(x1,y1);q.push(coor);maze[x1][y1]=1;		//标记为添上障碍物 while(!q.empty()){coor=q.front();		//取元素 q.pop();for(int i=0;i<4;i++){int x=coor.x+dx[i];		//偏移量得到邻居位置 int y=coor.y+dy[i];if(!maze[x][y]) 		//没有障碍物 {if(x==x2&&y==y2)		//到达终点 {route[x][y]=coor;			//标记前一位置 return 1;}else		//将该点加入队列中 {route[x][y]=coor;maze[x][y]=1;coordinate c(x,y);q.push(c);					}	}}} return 0;
}void outputroute(int tx,int ty)
{stack<coordinate> q;coordinate coor(tx,ty);while(coor.x!=-1){q.push(coor);		//当前坐标入栈 coor=route[coor.x][coor.y];			//坐标转换为前一位置 }while(!q.empty()){coor=q.top();cout<<"("<<coor.x-1<<", "<<coor.y-1<<")"<<endl;q.pop(); }
} 
int main(void)
{for(int i=1;i<=5;i++)for(int j=1;j<=5;j++)cin>>maze[i][j];for(int i=0;i<7;i++){maze[0][i]=1;maze[i][0]=1;maze[6][i]=1;maze[i][6]=1;}if(searchroute(1,1,5,5))outputroute(5,5);return 0;	
} 

这篇关于week2 A - Maze的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---