迷宫问题

5 计算机与信息工程系《高级语言课程设计》课程设计报告

环语句即可实现，如果是系统自动探索，并且在4个方向进行递归算法，即可实现寻找路径。

2.2.2结构设计及方法

用m行n列的m*n个正方格表示一个迷宫，其中划有斜线的方格表示不可通行，未划有斜线的方格表示可以通行。要寻找从入口到出口的一条最短路径的程序。

1.结构设计：

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

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

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

2.具体方法：

（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。在图结构中，将迷宫中的每个方格看作是一个顶点。不可通行的方格都是孤立顶点；相邻的可通行的方格所对应的顶点之间看作是有边相连。因此迷宫可以看作是由m*n个顶点及无向边构成的一个非连通的无向图。尽管图是不连通的，但不影响本问题的求解，而且本问题有解的条件是：入口顶点与出口顶点在同一个连通分量中。 图结构G中，G.adj[k]

6 计算机与信息工程系《高级语言课程设计》课程设计报告

表示编号为k的顶点的邻接情况的单链表的头指针；G.vexnum表示图G中的实际顶点数，而且具有如下关系：G.vexnum=A.rownum*A.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的。这样，当路径探索成功时，我们可以从出口顶点倒推出从入口到出口的一条路径来。当然要涉及到从顶点编号向方格坐标的反转换，这个公式在上面已经给出了。

2.2.3程序结构（流程图）

程序结构设计流程图如图2.1所示

7 计算机与信息工程系《高级语言课程设计》课程设计报告

图2.1流程图

8 计算机与信息工程系《高级语言课程设计》课程设计报告

3 模块功能的设计

3.1 模块设计

第一个模块—主函数main()的功能是：首先确定是人工还是系统自动探索，通过输入字符选定。选定后调用图形初始化函数，接着调用迷宫生成函数及迷宫显示函数。然后根据输入 的字符调用人工探索函数或自动探索函数，探索完毕进行结果处理，最后关闭图形系统，程序结束。

第二个模块—初始化函数Init()的功能是：由于迷宫是在图形方式下显示的，所以要进行图形初始化。

第三个模块—迷宫生成函数MapRand()的功能是： 用数组map表示一个迷宫，要随机生成迷宫，数组元素的值利用随机函数生成0或1的数。

第四个模块—迷宫显示函数PrMap()的功能： 根据数组map的值输出迷宫图，利用函数setfillstyle()设置图形实体填充样式bar（）函数输出矩形块。数组元素的下标为 矩形块的中心坐标，利用两重循环语句可以完成迷宫图的显示。

第五个模块—系统自动5FindWay()的功能：从下标（1，1）开始探索，依次按照右下、下、右、右上、左、左下、左上的顺序前进，若该方向上的值为0，则前进一步。

第六个模块—人工探索PeopleFind（）的功能：首先输出迷宫图以及人工控制操作图示， 红色探索出现在左上角，采用人工控制8个方向的移动，由于是8个方向，用光标键只能控制4个方向，为了统一采用了临近的8个字符，Q，W，E，A，D，Z，X，C代表8个方向，按了字符后，对应方向不是墙壁，可以将红色探索物移到相应的位置，按回车表示结果人工操作。如果此时map数组元素的坐标是出口，则yes的值为1，探索成功，否则值为0。由于探索物不停的移动，要在 新位置显示，并将走过的路恢复为白色通路，可以调用DrawPeople（&x,&y,n）完成.参数x和y代表所在的行坐标和列坐标,n代表所选的方向,根据n的值,将x和y进行相应的变化.

第七个模块—结果处理函数Result（）： 最终结果是找到和没找到两种情况，在程序中设计全局变量yes，根据yes的值进行处理。如果yes为0，调用函数NotFind（），显示 找到通路信息，否则调用函数Find（）。如果是系统自