迷宫问题大作业讲解

1、湖州师范学院信息工程学院数据结构课程设计大作业数据结构课程设计大作业20140821班题 目 迷宫问题专 业计算机科学与技术学生姓名姚鑫学 号2014082309指导教师樊艳芬完成日期2016/5/19湖州师范学院信息工程学院湖州师范学院信息工程学院数据结构课程设计大作业目录内容摘要1设计任务与技术要求 2总体设计方案2数据结构和算法的设计2程序清单3程序测试与调试7结论与体会10湖州师范学院信息工程学院数据结构课程设计大作业迷宫问题【内容摘要】在一个 m行， n列的迷宫中求从入口到出口的一条简单路径，即在求得路径上不能同时重复出 现同一通道。迷宫可用下图所示的方块来表示， 每个方块或者是通道

2、 （ 用空白方块表示 ）或者是墙 （用 带阴影的方块表示 ）。0和 1分别表示迷宫中的通道和墙。输出时简单路径用表示，起点用入表示，出口用出表示，墙用表示，可 走的路用 表示。输入 m，n,表示 m行 n列。再输入 m行 n列的迷宫（用 0和 1组成的矩阵表示） ，再输入迷宫 的起点和终点，输出迷宫（含有从起点到终点的简单路径） 。运用了深度优先搜索和递归的相关知 识。【关键字】 深度优先搜索 ，递归【Abstract 】Looking for a simple path from the entrance to the exit in a maze of M rows and N colum

3、ns, that is, the road could not be repeated at the same time in the path. A maze can be shown as diamonds in the following figures. Each diamond is either road or wall. Well , a blank diamond shows the road and a black diamond shows the wall .In the program ,zero represents road ,and one represents

4、wall.When we output, represents road, enter stands for starting point ,out stands for exit and represents wall. Well, stands for the way that we can choose.First we should type in m and n. Then type in rows of m and columns of n which can be represented by matrix made of zero and one. In the end, we

5、 should type in the starting point and exit.We have learned the information about Depth First Search and recursion.【 Key words】Depth First Search ， recursion湖州师范学院信息工程学院数据结构课程设计大作业一、实验内容概述 （ 设计任务与技术要求 ）以一个 mn 的长方阵表示迷宫， 0 和 1 分别表示迷宫中的通路和障碍。 设计一个程序， 对 任意设定的迷宫，求出一条从入口到出口的通路， 并把这条通路显示出来， 或得出没有通路的 结论。二、实

6、验目的概述 （ 总体设计方案 ）a）掌握迷宫问题的 DFS（深度优先搜索）解法。b）了解和熟悉深度优先搜索的思路。c）复习和熟悉二维数组的用法。d）使用图形来美化输出，使得输出一目了然。三、解题思路的描述 （ 数据结构和算法的设计 ）（1）总体思路：先输入迷宫多少行多少列（从1存到 n，0行0列以及 n+1行 n+1列设置为墙用 1 表示），再输入迷宫的入口和出口，然后递归调用DFS 函数（深度优先搜索）来寻找从起点到终点的路线。在搜索过程中把存迷宫的二维数组中每个点分别置为：0 尚未走过的路1 墙2 路线 然后判断是否存在这样一条路线，如果不存在，就输出“不存在从入口到出口的路线” ； 如果

7、存在，就输出迷宫（包括路线） 。并输出注释。 means the route means the road means the wall（2）数据结构的选择和描述： 选用了 int 类型数组，数组 a用来存储迷宫， 结构体 Point 用来 定义入口坐标和出口坐标， x 代表横坐标， y 代表纵坐标。 flag 用来记录 dfs 时是否找到 出口，即退出 dfs 的标志。（ flag 为 1 时找到出口，为 0 时没找到）（3）要算法的功能和描述： 采用了深度优先搜索 （ DFS）的思想。 每次搜索的方向依次为 右 下 左 上，每搜索一个点就标记为 2，若从该点的四个方向进行 dfs 都无法找

8、到出口， 就重新 标记为 0. ；（4）DFS的具体描述：1. 传入一个点的横纵坐标， 一开始就把传入的存迷宫的这个二维数组节点标记为2（路线），2. 判断是否为终点，如果是终点 flag 标记为 1（防止退出 DFS时走过的路线被还原 0）， 并跳出 DFS函数；否则什么也不做，继续往下运行；湖州师范学院信息工程学院数据结构课程设计大作业3. 向右搜索：判断右边相邻的结点是否违反要求（即是否是墙或者越界） ，如果不违反要 求，就把右边相邻的结点传入 DFS进行搜索；否则什么也不做，继续运行； 判断是否已经找到终点，若已经找到终点（ flag=1 ）直接跳出函数；4. 向下搜索：判断下边相邻的

9、结点是否违反要求（即是否是墙或者越界） ，如果不违反要 求，就把下边相邻的结点传入 DFS进行搜索；否则什么也不做，继续运行； 判断是否已经找到终点，若已经找到终点（ flag=1 ）直接跳出函数；5. 向左搜索：判断左边相邻的结点是否违反要求（即是否是墙或者越界） ，如果不违反要求，就把左边相邻的结点传入 DFS进行搜索；否则什么也不做，继续运行； 判断是否已经找到终点，若已经找到终点（ flag=1 ）直接跳出函数； 6. 向上搜索：判断上边相邻的结点是否违反要求（即是否是墙或者越界） ，如果不违反要求，就把上边相邻的结点传入 DFS进行搜索；否则什么也不做，继续运行； 判断是否已经找到终

10、点，若已经找到终点（ flag=1 ）直接跳出函数；7. 运行到这里还没找到终点表示此路不通， 把这点还原为没走过时的样子 （重新标记为 0）；四、 源程序清单（源程序中应该附有必要的注释）1) 源程序 #include typedef struct point int x; int y;Point;/ 迷宫中每个点Point start,end;int a4040;int m,n;int flag=0;void dfs(int x, int y)axy=2;if(x=end.x)&(y=end.y)flag=1;return ;if(y+1=n)&(axy+1=0) dfs(x,y+1);i

11、f(flag)/ 迷宫的入口与出口/ 输入时迷宫存储的数组/m: 行 n: 列/ sign of exit dfs退出的标志/ 深度优先搜索/ 表示 x 行 y 列这个位置已被走过/ 找到了出口/ 退出 dfs ，防止走过的路线被还原/ 向右搜索湖州师范学院信息工程学院数据结构课程设计大作业return;if(x+1=1)&(axy-1=0)dfs(x,y-1);if(flag)return;if(x-1=1)&(ax-1y=0)dfs(x-1,y);if(flag)return;axy=0;/ 向下搜索/ 向左搜索/ 向上搜索/ 此路不通，把这点还原为没走过时的样子int main()int

12、 i,j;printf( 请输入多少行多少列： ( m,n) (注：输入 0 0 结束 )n);while(scanf(%d%d,&m,&n)&(m|n)/ 输入 0 0 结束printf( 请输入迷宫： (1表示墙 0 表示路) n);for(i=0;i=m+1;i+)/ 输入迷宫for(j=0;j=n+1;j+)if(i=0|j=0|i=m+1|j=n+1) / 外面置为 1，即墙 aij=1;湖州师范学院信息工程学院数据结构课程设计大作业elsescanf(%d,&aij);2)printf( 请输入迷宫入口和出口 : x1 y1 x2 y2n); scanf(%d%d%d%d,&sta

13、rt.x,&start.y,&end.x,&end.y); dfs(start.x,start.y);if(!flag)printf( 不存在从入口到出口的路线 n);for(i=0;i=m+1;i+)for(j=0;j=n+1;j+)if(i=start.x&j=start.y)printf( 入);else if(i=end.x&j=end.y)printf( 出);else if(aij=1)printf( );else if(aij=0) printf( );else if(aij=2)printf( );printf(n); /printf( means the routen);pr

14、intf( means the roadn);printf( means the walln);return 0;/ 输入迷宫入口及出口 / 深度优先搜索 搜索路径/ 输出结果/ 入口 输出美化/ 出口 输出美化/ 墙 输出美化/ 路 输出美化/ 路线 输出美化换行/ 注释 算法的时间复杂度是什么？算法的空间复杂度是什么？为什么？ 答：空间复杂度：线性时间复杂度，具体看最长的那条路径长度。栈中维持单一路径 上的节点； 时间复杂度： O(m+1 )*(n+1) ) 注：存储迷宫所用的行数乘列数；湖州师范学院信息工程学院数据结构课程设计大作业3) 还可以扩充自己的想法，题目要求所编程序都能适用哪些

15、情况，如果做一些修改，还 能适合什么情况(能解决什么问题)？ 答：此代码还可以解决类似的寻找路径问题，且输出形象简洁。 做一些修改可以解决大多数的 DFS问题，如油田问题(记忆化搜索) ；4) 说明在这个程序中所使用的各变量、形式参数的具体含义及各子程序之间的调用关系 等。 答：1. 调用关系：调用 DFS函数，且在搜索的过程中一直调用，直到找到终点。2. 结构体 Point: 用来表示迷宫的每个结点，拥有成员变量 x,y 皆为整形。3. Start ， End：a) Start ：迷宫的起点；b) End: 迷宫的终点4. a4040 ：存储迷宫的数组；5. m,n：a) m 行 ;b) n

16、 列 ;6. flag: dfs 退出的标志 ;湖州师范学院信息工程学院数据结构课程设计大作业五、 程序调试及测试结果（ 1） 上机调试上述程序，总结在调试过程中出现的问题及解决方法1. 一开始没有定义 flag 导致找到从起点到终点的路线后无法输出路线。 因为在退出时都被还原了（还原为未走过时的样子了） ；2. 在美化输出时没有考虑到有些字符是普通的一个字符的两倍，导致输出完全不对；3. 没有考虑找不到从起点到终点的路线时的情况；4. 深度优先搜索时在搜索完四个方向都没有找到终点时忘记把这个点还原为 0 了；（ 2） 给出几组有代表性的数据，运行上述程序，查看运行结果，分析运行结果。截图 1

17、 5 5 的迷宫 从（ 1， 1）到（ 5，5）的路线7湖州师范学院信息工程学院数据结构课程设计大作业截图 2 5 5 的迷宫从（ 1， 1）到（ 3，5），不存在路线截图 3 书上的例子（ 69 的迷宫）从（ 1， 1）到（ 6，9）的路线8湖州师范学院信息工程学院数据结构课程设计大作业截图 4 书上的例子（ 69 的迷宫）从（ 1， 1）到（ 1，9）路线截图 5 12 18 的迷宫从（ 1， 1）到（ 12， 18 ）的路线9湖州师范学院信息工程学院数据结构课程设计大作业六、 结论与体会1） 在解决和设计本文题目所涉及到的问题时，你所采取的方法、手段和关键性的技术。采用了 DFS（深度优

18、先搜索） ，递归，输出的转化。2） 在调试程序的过程中你所遇到的问题及解决方法。1. 一开始没有定义 flag 导致找到从起点到终点的路线后无法输出路线。 因为在退出时都被还原了。 。（还原为未走过时的样子了） ；2. 在美化输出时没有考虑到有些字符是普通的一个字符的两倍，导致输出完全不对3. 没有考虑找不到从起点到终点的路线时的情况；4. 深度优先搜索时在搜索完四个方向都没有找到终点时忘记把这个点还原为0 了；（ 3） 关于程序的特色和改进设想。特色：1. 输出十分形象简洁， 只要输入迷宫以及起点终点就可以输出所求路线 （路线存在的 情况下）2. 采用了深度优先搜索，代码简洁，可读性高；3.

19、 深度优先搜索时的改变方向的方式采用了最简单， 易懂的方式， 虽然啰嗦， 但是可 读性好；改进设想：1. 可以使用 BFS（广度优先搜索 ） ，可以找出从起点到终点的最短路径，但是代码会变 得更长，用到了队列，可读性降低。2. 使用 c+的容器队列来使用 BFS,可是代码简洁。（4）其他需要说明的情况。任意大小的迷宫以及任意的起点与终点皆可计算出从起点到终点的路径（虽然不是最短 的）。小结 ：迷宫问题我一开始在输出的处理上有点问题，我一开始把存迷宫的 int 型二维数组 转存到 char 的字符型数组中去了，结果输出就乱套了，后来发现可以遍历的时候判断，如果 是 0 就用 printf 直接输出两个空格，是 1 就用 printf 输出，