1、 设计题目： 设计题目：迷宫系统迷宫系统 2012-5-28 一、一、问题描述：问题描述： 把一只老鼠从一个无顶盖的大盒子 （迷宫） 的入口处赶进迷宫。 迷宫中设置 了很多墙壁， 对前进方向形成了多处障碍。 在迷宫的唯一出口处放置了一块奶酪， 吸引老鼠在迷宫中寻找通路以达到出口。 如果从迷宫的入口到达出口， 途中不出 现行进方向错误， 则得到一条最佳路线。 我们利用非递归方法获得迷宫从入口到 出口的最佳路线。 二、需求分析：二、需求分析： 【基本需求】 （）设置可选择的入口及出口，具有良好的界面以便用户操作。 （）自动生成迷宫，迷宫中用不同的符号标志代表墙壁和通路。 （）利用非递归算法实现，
2、并输出有无通路两种情况下的迷宫路径， 便于用户 查看。 【简单分析】 （1）本程序中定义了三个二维数组。 一个迷宫数组， 两个标记数组。 对它们进行相同的初始化。 （2）程序使用 create()函数，系统自动创建一个大小确定的迷宫，该 迷宫有 A、B、C、D 四个门。任何两个门之间是否存在路径不能确 定，系统自动分配。 int row int col struct Point *next struct Point 入口截图: （3）输出的形式： 在有无通路时使用两种不同的标记路径方式，有通路时采用图 形输出，无通路时则采用标记数组 maze表示。 有通路的路径截图： 无通路的路径截图： 三、
3、概要设计：三、概要设计： 1、数据结构的设计 首先，在寻找迷宫路径的时候,当走到某一位置而不能再前进时,就 需要后退。因此，我们需要用“栈”的思想来满足这一要求。 其次，当成功找到路径时，我们需要用图形输出迷宫。在输出路径 时每个点之间必须要有联系，所以我们又用了“链表”的思想。 最后, 结合以上两点,在本程序中,我们应用了“链式栈”的思想， 用以 解决存放迷宫路径以及输出路径的问题。 2、算法的设计 （）创建迷宫： 用二维数组 Mazem+2n+2来表示迷宫矩阵，当数组元素 Mazeij=1 时，表示该位置是墙壁, 不能通行；当数组元素 Mazeij=0 时，表示该位置是通路。 （1im）(
4、1jn) 数组的第行、第 m+1 行、第列、第 n+1 列是迷宫的围墙。 建 立过程中调用库函数 rand()，产生随机数，从而自动生成迷宫。 （）路径查找： 使用链式栈来存储在试探的过程中所走过的路径。一旦需要回 退，可以从栈中取得刚才走过位置的坐标和前进方向。如果某个前进 方向走不通，则将位于栈顶的活动记录退栈，使得在前进路径上回退 一步，再尝试其他的允许方向，直至找到出口为止（有通路） 。如果 栈空则表示已经退回到开始位置（无通路） 。 （）路径输出： 有路径时， 用标记数组 mark输出。mark数组中各元素的 值与迷宫数组 Maze完全相同,此时我们采用图形输出。 具体算法如下所示： 假定 p、 q 为指向 Point 的指针， p 指向当前位置， q 指向下一位置。 当 p-row q-row 时，输出； 当 p-row row 时，输出； 当 p-col q-col 时， 输出； 当 p-col col 时， 输出； 没有路径时，用标记数
