迷宫问题大作业

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

2、阴影的方块表示）。0和1分别表示迷宫中的通道和墙。输出时简单路径用表示，起点用入表示，出口用出表示，墙用表示，可走的路用表示。输入mn,表示m行n歹U。再输入m行n列的迷宫（用0和1组成的矩阵表示），再输入迷宫的起点和终点，输出迷宫（含有从起点到终点的简单路径）。运用了深度优先搜索和递归的相关知识。【关键字】深度优先搜索，递归AbstractLookingforasimplepathfromtheentrancetotheexitinamazeofMrowsandNcolumns,thatis,theroadcouldnotberepeatedatthesametimeinthepath.Am

3、azecanbeshownasdiamondsinthefollowingfigures.Eachdiamondiseitherroadorwall.Well,ablankdiamondshowstheroadandablackdiamondshowsthewall.Intheprogram,zerorepresentsroad,andonerepresentswall.Whenweoutput,representsroad,enterstandsforstartingpoint,outstandsforexitand''representswall.Well,'

4、9;standsforthewaythatwecanchoose.Firstweshouldtypeinmandn.Thentypeinrowsofmandcolumnsofnwhichcanberepresentedbymatrixmadeofzeroandone.Intheend,weshouldtypeinthestartingpointandexit.WehavelearnedtheinformationaboutDepthFirstSearchandrecursion.KeywordsDepthFirstSearch,recursion1、 实验内容概述（设计任务与技术要求）以一个m

5、xn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，并把这条通路显示出来，或得出没有通路的结论。2、 实验目的概述（总体设计方案）a）掌握迷宫问题的DFS（深度优先搜索）解法。b）了解和熟悉深度优先搜索的思路。c）复习和熟悉二维数组的用法。d）使用图形来美化输出，使得输出一目了然。3、 解题思路的描述（数据结构和算法的设计）（1）总体思路：先输入迷宫多少行多少列（从1存到n,0行0列以及n+1行n+1列设置为墙用1表示），再输入迷宫的入口和出口，然后递归调用DFS函数（深度优先搜索）来寻找从起点到终点的路线。在搜索过程中把存迷宫的

6、二维数组中每个点分别置为：0尚未走过的路1墙2路线然后判断是否存在这样一条路线，如果不存在，就输出“不存在从入口到出口的路线”；如果存在，就输出迷宫（包括路线）。并输出注释。''meanstheroute''meanstheroad''meansthewall（2）数据结构的选择和描述：选用了int类型数组，数组a用来存储迷宫，结构体Point用来定义入口坐标和出口坐标，x代表横坐标，y代表纵坐标。flag用来记录dfs时是否找到出口，即退出dfs的标志。（flag为1时找到出口，为0时没找到）（3）要算法的功能和描述：采用了深度优先搜索（DFS

7、的思想。每次搜索的方向依次为右下左上，每搜索一个点就标记为2,若从该点的四个方向进行dfs都无法找到出口，就重新标记为0.;（4）DFS的具体描述：1 .传入一个点的横纵坐标，一开始就把传入的存迷宫的这个二维数组节点标记为2（路线），2 .判断是否为终点，如果是终点flag标记为1（防止退出DFS时走过的路线被还原0）,并跳出DFS函数；否则什么也不做，继续往下运行；3 .向右搜索：判断右边相邻的结点是否违反要求（即是否是墙或者越界），如果不违反要求，就把右边相邻的结点传入DFS进行搜索；否则什么也不做，继续运行；判断是否已经找到终点，若已经找到终点（flag=1）直接跳出函数；4 .向下搜索

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

9、终点（flag=1）直接跳出函数；7 .运行到这里还没找到终点表示此路不通，把这点还原为没走过时的样子（重新标记为0）;4、 源程序清单（源程序中应该附有必要的注释）(1)源程序#include<stdio.h>typedefstructpointintx;inty;Point;Pointstart,end;inta4040;intm,n;intflag=0;voiddfs(intx,inty)axy=2;if(x=end.x)&&(y=end.y)flag=1;return;if(y+1<=n)&&(axy+1=0)dfs(x,y+1);if

10、(flag)/迷宫中每个点/迷宫的入口与出口/输入时迷宫存储的数组m:行n:歹U/signofexitdfs退出的标志/深度优先搜索/表示x行y列这个位置已被走过/找到了出口/退出dfs,防止走过的路线被还原/向右搜索return;)if(x+1<=m)&&(ax+1y=0)dfs(x+1,y);)if(flag)return;)if(y-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

11、=0;)/向下搜索/向左搜索/向上搜索/此路不通，把这点还原为没走过时的样子intmain()inti,j;printf("请输入多少行多少列：(m,n)(注：输入00结束)n");while(scanf("%d%d”,&m,&n)&&(m|n)/输入00结束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,即墙a皿=1;elsescanf("%

12、d",&aij);printf("请输入迷宫入口和出口：x1y1x2y2n");scanf("%d%d%d%d",&start.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("入");elsei

13、f(i=end.x&&j=end.y)printf("出)elseif(aij=1)printf("");elseif(aij=0)printf("");elseif(aij=2)printf("");printf("n");/printf("''meanstherouten");printf("''meanstheroadn");printf("''meansthewalln");

14、return0;/输入迷宫入口及出口/深度优先搜索搜索路径/输出结果/入口输出美化出口输出美化/墙输出美化/路输出美化/路线输出美化换行/注释(2) 算法的时间复杂度是什么？算法的空间复杂度是什么？为什么?答：空间复杂度：线性时间复杂度，具体看最长的那条路径长度。栈中维持单一路径上的节点;时间复杂度：O(m+1)*(n+1)注：存储迷宫所用的行数乘列数;(3) 还可以扩充自己的想法，题目要求所编程序都能适用哪些情况，如果做一些修改，还能适合什么情况(能解决什么问题)？答：此代码还可以解决类似的寻找路径问题，且输出形象简洁。做一些修改可以解决大多数的DFS问题，如油田问题(记忆化搜索)；(4)

15、说明在这个程序中所使用的各变量、形式参数的具体含义及各子程序之间的调用关系等。答：1. 调用关系：调用DFS函数，且在搜索的过程中一直调用，直到找到终点。2. 结构体Point:用来表示迷宫的每个结点，拥有成员变量x,y皆为整形。3. Start,End:a) Start:迷宫的起点；b) End:迷宫的终点4. a4040:存储迷宫的数组；5. m,n：a) m行；b) n歹U;6. flag:dfs退出的标志；五、程序调试及测试结果（1） 上机调试上述程序，总结在调试过程中出现的问题及解决方法1 .一开始没有定义flag导致找到从起点到终点的路线后无法输出路线。因为在退出时都被还原了（还原

16、为未走过时的样子了）；2 .在美化输出时没有考虑到有些字符是普通的一个字符的两倍，导致输出完全不对；3 .没有考虑找不到从起点到终点的路线时的情况；4 .深度优先搜索时在搜索完四个方向都没有找到终点时忘记把这个点还原为0了;（2） 给出几组有代表性的数据，运行上述程序，查看运行结果，分析运行结果。截图15X5的迷宫从（1,1）到（5,5）的路线tC:U5er5Administrator,Desk±op健高巨至2exe睛输入多少行多少列:晴输入迷宫：（工表示墙口表示路）II1010601011aiq&&情输入迷宫入口和出口工WX2皿1135怀存在从人口到出口的路线人ne

17、ansr1n&ansJ1nesnsthethetherouteroaduall截图25X5的迷宫从（1,1）到（3,5）,不存在路线截图3书上的例子（6X9的迷宫）从（1,1）到（6,9）的路线截图4书上的例子（6X9的迷宫）从（1,1）到（1,9）路线截图512X18的迷宫从（1,1）到（12,18）的路线六、结论与体会（1） 在解决和设计本文题目所涉及到的问题时，你所采取的方法、手段和关键性的技术。采用了DFS（深度优先搜索），递归，输出的转化。（2） 在调试程序的过程中你所遇到的问题及解决方法。1 .一开始没有定义flag导致找到从起点到终点的路线后无法输出路线。因为在退出时都被

18、还原了。（还原为未走过时的样子了）；2 .在美化输出时没有考虑到有些字符是普通的一个字符的两倍，导致输出完全不对3 .没有考虑找不到从起点到终点的路线时的情况；4 .深度优先搜索时在搜索完四个方向都没有找到终点时忘记把这个点还原为0了;（3） 关于程序的特色和改进设想。特色：1 .输出十分形象简洁，只要输入迷宫以及起点终点就可以输出所求路线（路线存在的情况下）2 .采用了深度优先搜索，代码简洁，可读性高；3 .深度优先搜索时的改变方向的方式采用了最简单，易懂的方式，虽然啰嗦，但是可读性好；改进设想：1.可以使用BFS（广度优先搜索），可以找出从起点到终点的最短路径，但是代码会变得更长，用到了队列，可读性降低。2.使用C+的容器队列来使用BFS,可是代码简洁。（4）其他需要说明的情况。任意大小的迷宫以及任意的起点与终点皆可计算出从起点到终点的路径（虽然不是最短的）。结：迷宫问题我一开始在输出的处理上有点问题，我一开始把存迷宫的int型二维数组转存到char的字符型