迷宫问题大作业..doc

数据结构课程设计大作业 题 目 迷宫问题 专 业 计算机科学与技术 学生姓名 姚鑫 学 号 2014082309 指导教师 樊艳芬 完成日期 2016/5/19 湖州师范学院信息工程学院 目 录 内容摘要…………………………………………………………………………………………1 设计任务与技术要求 …………………………………………………………………………2 总体设计方案……………………………………………………………………………………2 数据结构和算法的设计…………………………………………………………………………2 程序清单…………………………………………………………………………………………3 程序测试与调试…………………………………………………………………………………7 结论与体会………………………………………………………………………………………10 迷宫问题 【内容摘要】 在一个m行，n列的迷宫中求从入口到出口的一条简单路径，即在求得路径上不能同时重复出现同一通道。迷宫可用下图所示的方块来表示，每个方块或者是通道(用空白方块表示)或者是墙(用带阴影的方块表示)。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 columns, 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 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 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  实验内容概述(设计任务与技术要求) 以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，并把这条通路显示出来，或得出没有通路的结论。 实验目的概述(总体设计方案) 掌握迷宫问题的DFS（深度优先搜索）解法。 了解和熟悉深度优先搜索的思路。 复习和熟悉二维数组的用法。 使用图形来美化输出，使得输出一目了然。 解题思路的描述(数据结构和算法的设计) 总体思路：先输入迷宫多少行多少列（从1存到n，0行0列以及n+1行n+1列设置为墙用1表示），再输入迷宫的入口和出口，然后递归调用DFS函数（深度优先搜索）来寻找从起点到终点的路线。在搜索过程中把存迷宫的二维数组中每个点分别置为： 0 尚未走过的路 1 墙 2 路线 然后判