数据结构课程设计---迷宫问题求解

《数据结构课程设计---迷宫问题求解》由会员分享，可在线阅读，更多相关《数据结构课程设计---迷宫问题求解（16页珍藏版）》请在毕设资料网上搜索。

1、 迷宫问题求解迷宫问题求解 一问题的提出：问题的提出： 人类建造迷宫已有 5000 年的历史。在世界的不同文化发展时期，这些奇特的 建筑物始终吸引人们沿着弯弯曲曲、困难重重的小路吃力地行走，寻找真相。关 于迷宫， 有一个引人入胜的希腊神话， 这也是为什么现今每当人们提到这个问题， 总是兴致勃勃（对于年青人，估计是 RPG 玩多了） 。这则神话讲的是，从前弥诺 斯王统治着克里特岛。有一年，他没有给海神波塞冬送去允诺的祭物公牛，海神 十分生气， 决意报复。 他附体在公牛身上， 勾引了弥诺斯王的妻子帕西法厄王后。 不久，王后生下一个牛首人身的怪物弥诺陶洛斯(Minotaur)。为了把怪物藏起来 避免

2、家丑外扬，弥诺斯王命令岛上最优秀的工匠代达罗斯造了一座迷宫：一所稀 奇古怪的地下房子，走廊离亮处越来越远，根本找不到出口。发狂的弥诺陶洛斯 在一堵堵墙壁之间徘徊游荡，左突右冲，以雅典王进贡的童男童女充饥。终于有 一天，雅典王子忒修斯(Theseus)带着宝剑冒充进贡的童男进入迷宫。他一路退 下弥诺斯王的女儿阿里阿德涅送给他的线团的线，杀死了牛头怪物弥诺陶洛斯， 又沿着这根线找到出口，活着离开迷宫. 一般的迷宫为二维平面图形,将迷宫的左上角作入口，右下角作出口，求出 从入口点到出口点的一条通路。迷宫的大小为 NN，N 预定义为常数，修改 N 的值可以改变迷宫的大小（只要不超过屏幕显示范围） ，而

3、程序不必做修改。用 白色表示可走的路，红色表示墙壁不可以通过。程序还设计了两种运行方式：一 种是由系统自动运行探索， 用递归方法实现； 另一种是直接按结果搜索探索通路， 颇有新意。 图 1 迷宫的图例 图 2 迷宫的求解老师指点 二问题的分析：问题的分析： 图 3 基本思想 本问题的求解，关键是如何找到求解任意两个点间，按照以上基本思想而走 出的路线。 按照这个路线， 我们可以通过图形函数来动态的显示迷宫的搜索过程。 计算机解迷宫解通常用的是“穷举求解”方法，即从入口出发，顺着某一个 方向进行探索，若能走通，则继续往前进，否则沿着原路退回，换一个方向继续 探索，直至出后位置，求得一条通路。假如

4、所有可能的通路都探索到位能到达出 口，则所设定的迷宫没有通路。 为此，我们先要处理地图问题。将地图中有墙的地方设为 1，而没墙的地方， 也即可以通行的地方设为 0，如：在我们的这个程序中的一个例子中，地图如下 显示： 图 4 地图 1 当然了，有了地图，下一步就是如何在地图中查询可行路线了。按照基本 思想，当前已走过的可行的应设为墙，以防止在程序的搜索过程中，其又按原路 返回，造成死循环。在我们的程序中，我们设走过的路的地图所在地为 2，如下 示： zmaprowcol=2; /* block current position */ 搜索路线， 当需要一个数组来存储可行路线了， 我们在程序中如下设定： struct int row; /* the row of the position */ int col; /* the col of the position */ pathmaxlength; 由基本思想，搜索中按东南西北的先后顺序，我们又定义一个结构体来进 行搜索中的换向，如下示： struct int row