*******************实践教学*******************兰州理工大学软件学院2012年春季学期算法与数据结构课程设计题目：迷宫问题专业班级：姓名：学号：指导教师：成绩：_______________I摘要在现实生活中，会遇到很多很多关于迷宫这样很复杂、很难解决的问题的问题。如果人工去解决这些问题，会很麻烦，花很长的时间，甚至无法解决。假如用计算机去解决，可以通过手动生成迷宫，也可以通过计算机随机的产生迷宫，最终退出。而且可以很快的求解迷宫，找到从入口到出口的通路，或者当没有通路时，得出没有通路的结论。找出通路之后，会显示出通路路经，而且以图示的方式显示出通路，这样会使人一目了然的看清此迷宫的通路。迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组maze[M+2][N+2],然后用它的前m行n列来存放元素，即可得到一个m×n的二维数组，这样(0,0)表示迷宫入口位置，(m-1,n-1)表示迷宫出口位置。关键词：迷宫；通路；二维数组；路径II序言随着社会经济的发展，信息化程度的不断深入，传统的人工求解迷宫问题已不能满足生活的需要。近几年，随着迷宫问题越来越复杂、科技也越来越发达，人们逐渐的开始用计算机求解迷宫问题。迷宫问题很复杂，但是人们又不得不去研究这个问题，因为人们的生活中需要它，离不开它。在迷宫路径的搜索过程中，首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索过的位置标记为2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法，如果找到路径，则为最短路径。III目录一、需求分析...........................................................................................................................................................51.1功能与数据需求..........................................................................................................................................51.1.1题目要求的功能...........................................................................................................................................51.1.2扩展功能......................................................................................................................................................51.2界面需求.....................................................................................................................................................61.3开发环境与运行需求..................................................................................................................................6二、概要设计...........................................................................................................................................................72.1主要数据结构..............................................................................................................................................72.2各模块函数说明..........................................................................................................................................8三、详细设计...........................................................................................................................................................9四、测试..............
