数据结构中的迷宫问题VIP免费

数据结构中的迷宫问题 作者:**pp2009-5-21 22:26:00 推荐迷宫问题最早出现在古希腊神话中。据说，半人半兽的英雄西修斯在克里特的迷宫中勇敢地杀死半人半牛的怪物，并循着绳索逃出迷宫。希腊史学家希罗多德曾探访过那里。他描述说，整个迷宫由 12 座带顶院落构成，所有的院落都由通道连接，形成 3000 个独立的“室”。后来的参观者也说，一旦进入迷宫，如果没有向导，根本无望走出。历史上，人们认为迷宫具有魔力。后来，迷宫成为游戏。在如今计算机非常普及的情况下，迷宫又以游戏程序的形式呈现在我们日常使用的电脑上。 解题思路解析： 在迷宫问题中，一个迷宫用二维数组 maze[size] [size]来存储，对当前位置（探索过程中某一时刻所在的位置）记为 maze[curpos.row][curpos.line]，如果 maze[curpos.row][curpos.line]=0则有通路，如果 maze[curpos.row][curpos.line]=1 则无通路。从入口 star 出发，可沿四个方向前进。 试探方向的变化 N(i-1,j) W(i,j-1) 位置（i,j） E(i,j+1) S(i+1,j) 0 表示E、1 表示S、2 表示W、三表示N。如果遇到 0 则可前进，遇 1 责受阻；按此规则求入口到某一确定出口的一条路径。算法的基本思想是：从迷宫的入口出发，进行判断，若当前位置可通（未走过的），则将当前位置插入栈顶，然后判断此位置是否为出口位置，如果是则结束整个运算，否则，改变当前位置到他的东临位置（即 0 方向）；否则如果当前位置不通，这时若栈不空且栈顶位置尚有其他位置未搜索，则设定新的当前位置为栈顶位置的下一邻块，若栈不空且栈顶位置四周不通，则删去栈顶位置，若栈不空，则重新测试新的栈顶位置，直到找到一个可通的邻块或栈空，如此重复判断，直到找到一条从入口到出口的一条路径或得到无路径的信息。 (1)需求分析 问题描述：以一个 size*size 的长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍。设计一个程序，对任意设定输入的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 在迷宫中求出从入口到出口的路径。经分析，一个简单的求解方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行搜索，直到所有可能的通路都探索到为止。即所谓的回溯法。 求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续...