《迷宫问题大作业Word版》由会员分享，可在线阅读，更多相关《迷宫问题大作业Word版（15页珍藏版）》请在金锄头文库上搜索。
1、传播优秀Word版文档 ，希望对您有帮助，可双击去除！ 数据结构课程设计大作业20140821班 题 目 迷宫问题 专 业 计算机科学与技术 学生姓名 姚鑫 学 号 2014082309 指导教师 樊艳芬 完成日期 2016/5/19 湖州师范学院信息工程学院目 录内容摘要1设计任务与技术要求 2总体设计方案2数据结构和算法的设计2程序清单3程序测试与调试7结论与体会10迷宫问题【内容摘要】在一个m行，n列的迷宫中求从入口到出口的一条简单路径，即在求得路径上不能同时重复出现同一通道。迷宫可用下图所示的方块来表示，每个方块或者是通道(用空白方块表示)或者是墙(用带阴影的方块表示)。0和1分别表示
2、迷宫中的通道和墙。输出时简单路径用表示，起点用入表示，出口用出表示，墙用表示，可走的路用 表示。 输入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 columns, that is, the road could not be repeated at the s
3、ame 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 wall. When we output, represents road, enter stands
4、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 should type in the starting point and exit.We have
5、 learned the information about Depth First Search and recursion.【Key words】Depth First Search ，recursion一、 实验内容概述(设计任务与技术要求) 以一个mn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，并把这条通路显示出来，或得出没有通路的结论。二、 实验目的概述(总体设计方案) a) 掌握迷宫问题的DFS（深度优先搜索）解法。b) 了解和熟悉深度优先搜索的思路。c) 复习和熟悉二维数组的用法。d) 使用图形来美化输出，使得输
6、出一目了然。三、 解题思路的描述(数据结构和算法的设计) （1） 总体思路：先输入迷宫多少行多少列（从1存到n，0行0列以及n+1行n+1列设置为墙用1表示），再输入迷宫的入口和出口，然后递归调用DFS函数（深度优先搜索）来寻找从起点到终点的路线。在搜索过程中把存迷宫的二维数组中每个点分别置为：0 尚未走过的路 1 墙2 路线然后判断是否存在这样一条路线，如果不存在，就输出“不存在从入口到出口的路线”；如果存在，就输出迷宫（包括路线）。并输出注释。 means the route means the road means the wall（2） 数据结构的选择和描述：选用了int类型数组，数组
7、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函数；否则什么也不
8、做，继续往下运行；3.向右搜索：判断右边相邻的结点是否违反要求（即是否是墙或者越界），如果不违反要求，就把右边相邻的结点传入DFS进行搜索；否则什么也不做，继续运行；判断是否已经找到终点，若已经找到终点（flag=1）直接跳出函数；4.向下搜索：判断下边相邻的结点是否违反要求（即是否是墙或者越界），如果不违反要求，就把下边相邻的结点传入DFS进行搜索；否则什么也不做，继续运行；判断是否已经找到终点，若已经找到终点（flag=1）直接跳出函数；5.向左搜索：判断左边相邻的结点是否违反要求（即是否是墙或者越界），如果不违反要求，就把左边相邻的结点传入DFS进行搜索；否则什么也不做，继续运行；判断是
9、否已经找到终点，若已经找到终点（flag=1）直接跳出函数；6.向上搜索：判断上边相邻的结点是否违反要求（即是否是墙或者越界），如果不违反要求，就把上边相邻的结点传入DFS进行搜索；否则什么也不做，继续运行；判断是否已经找到终点，若已经找到终点（flag=1）直接跳出函数；7.运行到这里还没找到终点表示此路不通，把这点还原为没走过时的样子（重新标记为0）；四、 源程序清单（源程序中应该附有必要的注释）（1） 源程序#includetypedef struct pointint x;int y;Point;/迷宫中每个点 Point start,end; /迷宫的入口与出口 int a4040;
10、 /输入时迷宫存储的数组 int m,n; /m:行 n:列 int flag=0; / sign of exit dfs退出的标志 void dfs(int x, int y) /深度优先搜索 axy=2;/表示x行y列这个位置已被走过if(x=end.x)&(y=end.y)/找到了出口 flag=1;/退出dfs，防止走过的路线被还原 return ;if(y+1=n)&(axy+1=0)/向右搜索 dfs(x,y+1);if(flag)return;if(x+1=1)&(axy-1=0)/向左搜索 dfs(x,y-1);if(flag)return;if(x-1=1)&(ax-1y=0
11、)/向上搜索 dfs(x-1,y);if(flag)return;axy=0;/此路不通，把这点还原为没走过时的样子 int main()int 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);printf(请输入迷宫入口和出口: x1 y
12、1 x2 y2n);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(入);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); /注释
