迷宫问题大作业

湖州师范学院信息工程学院数据结构课程设计大作业数据结构课程设计大作业20140821班题目迷宫问题专业计算机科学与技术学生姓名姚鑫学号2014082309指导教师樊艳芬完成日期2016/5/19湖州师范学院信息工程学院湖州师范学院信息工程学院数据结构课程设计大作业目录内容摘要…………………………………………………………………………………………1设计任务与技术要求…………………………………………………………………………2总体设计方案……………………………………………………………………………………2数据结构和算法的设计…………………………………………………………………………2程序清单…………………………………………………………………………………………3程序测试与调试…………………………………………………………………………………7结论与体会………………………………………………………………………………………10湖州师范学院信息工程学院数据结构课程设计大作业1迷宫问题【内容摘要】在一个m行，n列的迷宫中求从入口到出口的一条简单路径，即在求得路径上不能同时重复出现同一通道。迷宫可用下图所示的方块来表示，每个方块或者是通道(用空白方块表示)或者是墙(用带阴影的方块表示)。0和1分别表示迷宫中的通道和墙。输出时简单路径用‘☆’表示，起点用‘入’表示，出口用‘出’表示，墙用‘■’表示，可走的路用‘’表示。输入m，n,表示m行n列。再输入m行n列的迷宫（用0和1组成的矩阵表示），再输入迷宫的起点和终点，输出迷宫（含有从起点到终点的简单路径）。运用了深度优先搜索和递归的相关知识。【关键字】深度优先搜索，递归【Abstract】LookingforasimplepathfromtheentrancetotheexitinamazeofMrowsandNcolumns,thatis,theroadcouldnotberepeatedatthesametimeinthepath.Amazecanbeshownasdiamondsinthefollowingfigures.Eachdiamondiseitherroadorwall.Well,ablankdiamondshowstheroadandablackdiamondshowsthewall.Intheprogram,zerorepresentsroad,andonerepresentswall.Whenweoutput,‘☆’representsroad,enterstandsforstartingpoint,outstandsforexitand‘■’representswall.Well,‘’standsforthewaythatwecanchoose.Firstweshouldtypeinmandn.Thentypeinrowsofmandcolumnsofnwhichcanberepresentedbymatrixmadeofzeroandone.Intheend,weshouldtypeinthestartingpointandexit.WehavelearnedtheinformationaboutDepthFirstSearchandrecursion.【Keywords】DepthFirstSearch，recursion湖州师范学院信息工程学院数据结构课程设计大作业2一、实验内容概述(设计任务与技术要求)以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，并把这条通路显示出来，或得出没有通路的结论。二、实验目的概述(总体设计方案)a)掌握迷宫问题的DFS（深度优先搜索）解法。b)了解和熟悉深度优先搜索的思路。c)复习和熟悉二维数组的用法。d)使用图形来美化输出，使得输出一目了然。三、解题思路的描述(数据结构和算法的设计)（1）总体思路：先输入迷宫多少行多少列（从1存到n，0行0列以及n+1行n+1列设置为墙用1表示），再输入迷宫的入口和出口，然后递归调用DFS函数（深度优先搜索）来寻找从起点到终点的路线。在搜索过程中把存迷宫的二维数组中每个点分别置为：0尚未走过的路1墙2路线然后判断是否存在这样一条路线，如果不存在，就输出“不存在从入口到出口的路线”；如果存在，就输出迷宫（包括路线）。并输出注释。'☆'meanstheroute''meanstheroad'■'meansthewall（2）数据结构的选择和描述：选用了int类型数组，数组a用来存储迷宫，结构体Point用来定义入口坐标和出口坐标，x代表横坐标，y代表纵坐标。flag用来记录dfs时是否找到出口，即退出dfs的标志。（flag为1时找到出口，为0时没找到）（3）要算法的功能和描述：采用了深度优先搜索（DFS）的思想。每次搜索的方向依次为右下左上，每搜索一个点就标记为2，若从该点的四个方向进行dfs都无法找到出口，就重新标记为0.；（4）DFS的具体描述：1.传入一个点的横纵坐标，一开始就把传入的存迷宫的这个二维数组节点标记为2（路线），2.判断是否为终点，如果是终点flag标记为1（防止退出DFS时走过的路线被还原0），并跳出DFS函数；否则什么也不做，继续往下运行；湖州师范学院信息工程学院数据结构课程设计大作业33.向右搜索：判断右边相邻的结点是否违反要求（即是否是墙或者越界），如果不违反要求，就把右边相邻的结点传入DFS进行搜索；否则什么也不做，继续运行；判断是否已经找到终点，若已经找到终点（flag==1）直接跳出函数；4.向下搜索：判断下边相邻的结点是否违反要求（即是否是墙或者越界），如果不违反要求，就把下边相邻的结点传入DFS进行搜索；否则什么也不做，继续运行；判断是否已经找到终点，若已经找到终点（flag==1）直接跳出函数；5.向左搜索：判断左边相邻的结点是否违反要求（即是否是墙或者越界），如果不违反要求，就把左边相邻的结点传入DFS进行搜索；否则什么也不做，继续运行；判断是否已经找到终点，若已经找到终点（flag==1）直接跳出函数；6.向上搜索：判断上边相邻的结点是否违反要求（即是否是墙或者越界），如果不违反要求，就把上边相邻的结点传入DFS进行搜索；否则什么也不做，继续运行；判断是否已经找到终点，若已经找到终点（flag==1）直接跳出函数；7.运行到这里还没找到终点表示此路不通，把这点还原为没走过时的样子（重新标记为0）；四、源程序清单（源程序中应该附有必要的注释）（1）源程序#includestdio.htypedefstructpoint{intx;inty;}Point;//迷宫中每个点Pointstart,end;//迷宫的入口与出口inta[40][40];//输入时迷宫存储的数组intm,n;//m:行n:列intflag=0;//signofexitdfs退出的标志voiddfs(intx,inty)//深度优先搜索{a[x][y]=2;//表示x行y列这个位置已被走过if((x==end.x)&&(y==end.y)){//找到了出口flag=1;//退出dfs，防止走过的路线被还原return;}if((y+1=n)&&(a[x][y+1]==0)){//向右搜索dfs(x,y+1);}if(flag){湖州师范学院信息工程学院数据结构课程设计大作业4return;}if((x+1=m)&&(a[x+1][y]==0)){//向下搜索dfs(x+1,y);}if(flag){return;}if((y-1=1)&&(a[x][y-1]==0)){//向左搜索dfs(x,y-1);}if(flag){return;}if((x-1=1)&&(a[x-1][y]==0)){//向上搜索dfs(x-1,y);}if(flag){return;}a[x][y]=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[i][j]=1;湖州师范学院信息工程学院数据结构课程设计大作业5}else{scanf(%d,&a[i][j]);}}}printf(请输入迷宫入口和出口:x1y1x2y2\n);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(入);}elseif(i==end.x&&j==end.y){//出口输出美化printf(出);}elseif(a[i][j]==1){//墙输出美化printf(■);}elseif(a[i][j]==0){//路输出美化printf();}elseif(a[i][j]==2){//路线输出美化printf(☆);}}printf(\n);//换行}printf('☆'meanstheroute\n);//注释printf(''meanstheroad\n);printf('■'meansthewall\n);}return0;}（2）算法的时间复杂度是什么？算法的空间复杂度是什么？为什么？答：空间复杂度：线性时间复杂度，具体看最长的那条路径长度。栈中维持单一路径上的节点；时间复杂度：O（(m+1)*(n+1)）注：存储迷宫所用的行数乘列数；湖州师范学院信息工程学院数据结构课程设计大作业6（3）还可以扩充自己的想法，题目要求所编程序都能适用哪些情况，如果做一些修改，还能适合什么情况（能解决什么问题）？答：此代码还可以解决类似的寻找路径问题，且输出形象简洁。做一些修改可以解决大多数的DFS问题，如油田问题（记忆化搜索）；（4）说明在这个程序中所使用的各变量、形式参数的具体含义及各子程序之间的调用关系等。答：1.调用关系：调用DFS函数，且在搜索的过程中一直调用，直到找到终点。2.结构体Point:用来表示迷宫的每个结点，拥有成员变量x,y皆为整形。3.Start，End：a)Start：迷宫的起点；b)End:迷宫的终点4.a[40][40]：存储迷宫的数组；5.m,n：a)m行;b)n列;6.flag:dfs退出的标志;湖州师范学院信息工程学院数据结构课程设计大作业7五、程序调试及测试结果（1）上机调试上述程序，总结在调试过程中出现的问题及解决方法1.一开始没有定义flag导致找到从起点到终点的路线后无法输出路线。因为在退出时都被还原了（还原为未走过时的样子了）；2.在美化输出时没有考虑到有些字符是普通的一个字符的两倍，导致输出完全不对；3.没有考虑找不到从起点到终点的路线时的情况；4.深度优先搜索时在搜索完四个方向都没有找到终点时忘记把这个点还原为0了；（2）给出几组有代表性的数据，运行上述程序，查看运行结果，分析运行结果。截图15×5的迷宫从（1，1）到（5，5）的路线湖州师范学院信息工程学院数据结构课程设计大作业8截图25×5的迷宫从（1，1）到（3，5），不存在路线截图3书上的例子（6×9的迷宫）从（1，1）到（6，9）的路线湖州师范学院信息工程学院数据结构课程设计大作业9截图4书上的例子（6×9的迷宫）从（1，1）到（1，9）路线截图512×18的迷宫从（1，1