迷宫问题大作业

《迷宫问题大作业》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、湖州师范学院信息工程学院数据结构课程设计大作业数据结构课程设计大作业20140821班题目迷宫问题专业计算机科学与技术学生姓名姚鑫学号2014082309指导教师樊艳芬完成日期2016/5/19湖州师范学院信息工程学院11湖州师范学院信息工程学院数据结构课程设计大作业目录内容摘要…………………………………………………………………………………………1设计任务与技术要求…………………………………………………………………………2总体设计方案……………………………………………………………………………………2数据结构和算

2、法的设计…………………………………………………………………………2程序清单…………………………………………………………………………………………3程序测试与调试…………………………………………………………………………………7结论与体会………………………………………………………………………………………1011湖州师范学院信息工程学院数据结构课程设计大作业迷宫问题【内容摘要】在一个m行，n列的迷宫中求从入口到出口的一条简单路径，即在求得路径上不能同时重复出现同一通道。迷宫可用下图所示的方块来表示，每个方块或者是通道(

3、用空白方块表示)或者是墙(用带阴影的方块表示)。0和1分别表示迷宫中的通道和墙。输出时简单路径用‘☆’表示，起点用‘入’表示，出口用‘出’表示，墙用‘■’表示，可走的路用‘’表示。输入m，n,表示m行n列。再输入m行n列的迷宫（用0和1组成的矩阵表示），再输入迷宫的起点和终点，输出迷宫（含有从起点到终点的简单路径）。运用了深度优先搜索和递归的相关知识。【关键字】深度优先搜索，递归【Abstract】LookingforasimplepathfromtheentrancetotheexitinamazeofMro

4、wsandNcolumns,thatis,theroadcouldnotberepeatedatthesametimeinthepath.Amazecanbeshownasdiamondsinthefollowingfigures.Eachdiamondiseitherroadorwall.Well,ablankdiamondshowstheroadandablackdiamondshowsthewall.Intheprogram,zerorepresentsroad,andonerepresentswall.

5、Whenweoutput,‘☆’representsroad,enterstandsforstartingpoint,outstandsforexitand‘■’representswall.Well,‘’standsforthewaythatwecanchoose.Firstweshouldtypeinmandn.Thentypeinrowsofmandcolumnsofnwhichcanberepresentedbymatrixmadeofzeroandone.Intheend,weshouldtypein

6、thestartingpointandexit.WehavelearnedtheinformationaboutDepthFirstSearchandrecursion.【Keywords】DepthFirstSearch，recursion11湖州师范学院信息工程学院数据结构课程设计大作业一、实验内容概述(设计任务与技术要求)以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，并把这条通路显示出来，或得出没有通路的结论。二、实验目的概述(

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

8、“不存在从入口到出口的路线”；如果存在，就输出迷宫（包括路线）。并输出注释。'☆'meanstheroute''meanstheroad'■'meansthewall（2）数据结构的选择和描述：选用了int类型数组，数组a用来存储迷宫，结构体Point用来定义入口坐标和出口坐标，x代表横坐标，y代表纵坐标。flag用来记录dfs时是否找到出口，即退出dfs的标志。（flag为1时找到出