迷宫问题的求解

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

1、迷宫问题求解一．问题描述：请设计一个算法实现迷宫问题求解。二．需求分析：程序可实现用户与计算机的交互过程。在计算机显示提示信息后，可由用户输入迷宫的大小与形态，以“0”表示墙壁，以“1”表示通路。利用栈操作寻找一条从入口至出口的通路，最终输出带有路线的迷宫。三．算法思想：1.栈的设计：用计算机解迷宫问题时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通则继续向前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需

2、要用一个后进先出的结构来保存从入口到当前位置的路径。因此，可以利用“栈”来求解迷宫问题。2.表示迷宫的数据结构：设迷宫为m行n列，利用maze[m][n]来表示一个迷宫，maze[i][j]=0或1;其中0表示墙壁（不通），1表示通路，当从某点向下试探时，中间点有4个方向可以试探，（见图）而四个角点有2个方向，其它边缘点有3个方向，为使问题简单化，用maze[m+2][n+2]来表示迷宫，而迷宫的四周的值全部为0。这样做可使问题简化，每个点的试探方向全部为4，不用再判断当前点的试探方向有几个，同时与迷

3、宫周围是墙壁这一实际问题相一致。012345678900000000000101000100002011010000030111111100401100100005001110111060100111110700000000003.试探方向：在上述表示迷宫的情况下，每个点有4个方向去试探，如当前点的坐标(x,y)，与其相邻的4个点的坐标都可根据与该点的相邻方位而得到，如图所示。因为出口在（m，n），因此试探顺序规定为：从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题，方便的求出新点的坐标

4、，将从正东开始沿顺时针进行的这4个方向（用0，1，2，3表示东、南、西、北）的坐标增量放在一个结构数组direct[4]中，在该数组中，每个元素有两个域组成，x：横坐标增量，y：纵坐标增量。4.防止重复到达某点，以避免发生死循环：定义“足迹”函数，在到达某点（i,j）后将使maze[i][j]置为-1，以便区别未到达过的点，起到防止走重复点的目的。二．概要设计：1.栈的抽象数据类型的定义：ADTStack{数据对象：D={ai

5、ai∈ElemSet,i=1,2,...n,n≥0}数据关系：R1={

6、i-1,ai>

7、ai-1∈D,i=1,2,...n}基本操作：InitStack(&S)操作结果：构造一个空栈S。StackEmpty(S)初始条件：栈S已存在。操作结果：若S为空栈，则返回1，否则返回0。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。}ADTStack2.迷宫部分的函数功能：Pass(b)当迷宫m的b点的序号为1(可通过路径)，返回1，否则返回0。FootPri

8、nt(a)使迷宫m的a点的序号变为足迹(curstep)，表示经过。NextPos(c，di)根据当前位置及移动方向，返回下一位置。MarkPrint(b)使迷宫m的b点的序号变为-1(不能通过的路径)。MazePath(start，end)若迷宫maze中存在从入口start到出口end的通道，则求得一条。Print(x，y)输出迷宫。二．程序代码：#include#include#include#include

9、#defineMAXLENGTH15//设迷宫的最大行列数为15typedefintMazeType[MAXLENGTH][MAXLENGTH];//迷宫数组[行][列]typedefstruct{//迷宫坐标位置类型intx;//行值inty;//列值}PosType;typedefstruct{//栈的元素类型intord;//通道块在路径上的“序号”PosTypeseat;//通道块在迷宫中的“坐标位置”intdi;//从此通道块走向下一通道块的“方向”(0～3表示东～北)}SElemType;

10、MazeTypem;//迷宫数组intcurstep=1;//当前足迹,初值为1//*****************栈的定义******************#defineSTACK_INIT_SIZE10//存储空间初始分配量#defineSTACKINCREMENT2//存储空间分配增量typedefstructSqStack{//顺序栈SElemType*base;//在栈构造之前和销毁之后，base的值为NULLSElemType*top;/