C++迷宫求解[2023-01-26]

（四）迷宫求解（****）

1****、问题描述：

以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个C++语言程序，对任意设定的迷宫，求出一条从入口到出口的最短路径通路，或得出没有通路的结论。 为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。求得的通路以三元组(i,j,d)的形式输出，其中(i,j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。也可以采用图形方式显示。

基本要求：

1、迷宫的规格（即行数与列数）,状态设置(即各方格能否通行的状态)，以及入口和出口的位置，均应由输入随机确定。

2、求得的最短路径，应该以从入口到出口的路径上的各个方格的坐标的线性序列输出。当无通路时，应该报告无路径的信息。

3、尽量采用结构化程序设计方法，要求对各个模块的功能及参数作必要的说明。

实现提示一：

可以用二维数组来存储迷宫数据，借助栈先入后出的特性保存迷宫搜索程中已走过的路径信息，以便在遇到障碍时沿原路返回，在搜索结束后输出栈中保存的最终路径。

实现提示二：

1、迷宫可以采用matrix类型的二维数组A表示。A.rownum与A.colnum分别表示迷宫的实际的行数与列数。而A.maze[i][j]表示迷宫中第i行第j列的一个方格，用A.maze[i][j]=0表示该方格可以通行，用A.maze[i][j]=1表示该方格不可以通行。

2、由于要寻找从入口到出口的一条最短路径，最好将迷宫看作是一个图结构。则问题转化为寻找从对应于入口顶点到对应于出口顶点的一条最短路径的问题。该问题可以采用从入口顶点出发，进行广度优先搜索遍历，直到遇到出口顶点或者遍历完毕也没有遇到出口顶点为止。这二种情况分别对应于最短路径探索成功与查无通路的事实。

3、基于上述分析，涉及到数据结构的转换，即将二维数组表示的迷宫A转换为以adjlist 类型的邻接表表示的图结构G。在图结构中，将迷宫中的每个方格看作是一个顶点。不可通行的方格都是孤立顶点；相邻的可通行的方格所对应的顶点之间看作是有边相连。因此迷宫可以看作是由mn个顶点及无向边构成的一个非连通的无向图。尽管图是不连通的，但不影响本问题的求解，而且本问题有解的条件是：入口顶点与出口顶点在同一个连通分量中。 图结构G中，G.adj[k]表示编号为k的顶点的邻接情况的单链表的头指针；G.vexnum表示图G中的实际顶点数，而且具有如下关系：G.vexnum=A.rownumA.colnum

4、为了避免迷宫数据的重复输入，应使A能够自动地转换为G。因此应该设计一个转换算法create_adjlist(A,G)。而图结构中顶点是要编号的，约定以行为序，顺序给迷宫A中的方格所对应的顶点编号。这样迷宫中方格的坐标（即行row和列col）与图G中所对应的顶点的编号（即verno）之间具有如下关系：

verno=（row-1）* n + col

row=（verno-1）/ n + 1

col=（verno-1）% n + 1

5.在广度优先搜索遍历求解最短路径过程中，应该设置一个队列queue作为辅助数据结构；路径采用一个整数数组pred来表示。这二个数据结构的存储结构类型均为list类型，其说明定义如下：typedef int list[MAXVER]；

队列queue应该设置front和rear分别指示列首与列尾，queue[k]表示第k个入列的顶点编号。采用pred记录路径，pred[i]表示顶点i在广度优先搜索遍历过程中的前趋顶点的编号，它表明是经过边（pred[i]，i）达到顶点i的。这样，当路径探索成功时，可以从出口顶点倒推出从入口到出口的一条路径来。

源码

https://pan.baidu.com/s/1pq1Nwwo0hlc_J84F93HM4A?pwd=1111