合肥学院 计算机科学与技术系 课 程 设 计 报 告 2 0 0 8 ～2 0 0 9 学年第二学期 课程 数据结构与算法 课程设 计 名 称 迷宫问题 学生名称 陈建华 专业班级 0 8 计本（2 ）班 指导教师 王昆仑 2 0 1 0 年 6 月 一、问题分析和任务定义 1．题目：迷宫的生成与路由。生成一个 N*M（N 行 M 列）的迷宫，0 和 1 分别表示迷宫中的通路和障碍，设计一个程序，完成迷宫的组织与存储，并实现迷宫的路由算法。即对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论 2.设计要求：(1)N和M是用户可配置的，缺省值为50和50。(2)迷宫的入口和出口分别在左上角和右下角。(3)求得的通路以二元组( i , j )的形式输出，其中（i, j）指示迷宫中的一个坐标。(4) 以二维数组存储迷宫数据。 3.问题描述：迷宫是一个矩形区域如图（a）所示，它有一个入口和一个出口，其内部包含能穿越的强或障碍。迷宫老鼠问题就是要寻找一条从入口到出口的路径。 对这样的矩形迷宫，可以用 N*M 的矩阵来描述，N 和 M 分别代表迷宫的行数和列数。这样，迷宫中的每一个位置都可以用行号和列号来指定。（1，1）表示入口位置，（n,m）表示出口位置；从入口到出口的路径则是由一个位置构成的，每个位置上都没有障碍，且每个位置（第一个除外）都是前一个位置的东、南、西或北的邻居。 为了描述迷宫中位置（i,j）处有无障碍，规定：当位置（i,j）处有一个障碍时，其值为 1，否则为 0。这样，如图（a）所示的迷宫就可以用图（b）所示的矩阵来描述。其中，a11=0 表示入口,anm=0 表示出口；若aij 表示从入口到出口路径上的某个位置，则应该有aij=0 经分析，一个简单的求解方法是：从入口出发，沿某一方向 进 行探 索 ，若能走 通，则继续 向 前走 ；否则沿原 路返 回 ，换 一方向 再 进 行搜 索 ，直 到所有可能的通路都探 索 到为止 。即所谓 的回 溯 法。 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 1 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 (a) (b) 4.测 试 用例 ： 手 动 绘 制 迷宫正 确 的输入数据： 0 0 0 0 1 0 1...
VIP
