基于栈实现的迷宫问题

《基于栈实现的迷宫问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于栈实现的迷宫问题1、问题描述：在一个二维阵列构成的迷宫里，数组元素仅有0和1构成，其中0表示可通行的路径，1代表障碍。另外，定义左上角是迷宫的入口，右下角是迷宫的出口，在迷宫里面只允许上下左右四个方向行走，请找出一条通路。2、算法基木思想：由于计算机解迷宫吋，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退lH

2、,显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中采用“栈”进行求解。2.1、迷宫构建：为了避免每走

3、一步便需判断是否走出迷宫的麻烦，将所创建的迷宫用1包围起来。2.2、位置搜索：每到一处，总让它按上、下、左、右4个方向试探下一个位置；如果某方向可以通过，即该方向上的元素为0,则前进一步，并在新位置上继续进行搜索；如果4个方向都走不通或曾经走过，则后退一步，在原來的位置上继续试探下一位置。每前进一步，都要进行判断：若前进到了岀口处，则说明找到了一条通路；若退回到了入口处，则说明不存在通路。3、算法运行环境：VC++6.04、主要函数：Mazepath函数：求解迷宫maze中,从入口start到出口end的一条路径若存在，返回TRUE,否则返回FALSEInitMaze函数：创建初始矩阵按照

4、用户输入的数据构建0/1矩阵，并在矩阵四周添加一圈1作为围墙。Pass函数：判断当前节点能否通过。Footprint函数：对于走过的节点用嚎进行标记。MarkPrint函数：对于不能通过的节点用#进行标记。Nextpos函数；返回当前节点的下一结点，对应东、四、南、北四个方向。Printmaze函数：打印迷宫信息，存在的通路用即表示。5、算法举例：5.1、输入的矩阵:enterthenazesdata“9彳丁8列〉010101100001110001001001001001011100011110110010010001101110000100101100运行结果:***«##«**#u#

5、**«utttt*«###«#*«#ft*«#unn***«tt«#**第诩.第诩.第2歹！第3歹！第3歹！第4歹！第4歹！第5歹！第5歹！第5歹I第5歹I第5歹I第6歹I第7歹I第7歹I第8歹I第丄步:第丄行,第2步：第2行，第3步:第2行，第4步：第2行，第5步：第3行，第6步：第3行，第?步：第4行，第8步：第4行，第9步：第5行，第10步：第6行,第“步：第?行,第丄2步:第8行,第丄3步:第8行,第14步：第8行,第15步:第9行,第16步：第9行,5.2、输入的矩阵:enterthemazesdata：<9彳丁8列〉0101110101101000010011100001010

6、01101001000100101010110101110010100000111运行结果：没有找到通路6、算法复杂度分析：(n为迷宫的行数，m为迷宫的列数)走迷宫的时间复杂度：O(n*m*2)o附迷宫问题源程序//base.h#include#include#include#inelude〃函数结果状态代码#define#define#define#define#define#defineTRUE1FALSE0OK1ERROR0INFEASIBLE・1OVERFLOW-2〃函数的返冋值typedefintSta

7、tus;〃下一个通道方向typedefintDirectiveType;//stack.h〃迷宫大小#defineRANGE100#defineSTACKJNIT.SIZE100#defineSTACKINCREMENT10//栈的顺序存储实现typedefstruct{introw;intcol;[PosType;typedefstruct{intstep;〃当前位置在路径上的”序号“Posiypeseat;〃当前的坐标位置DirectiveTypedi；〃往下一个坐标位置的方向)SElemType;typedefstruct{SElemType*base;SElemType*top

8、;intstacksize;JSqStack;//栈的基本操作的算法实现StatusInitStack(SqStack&s){s.base=(SElemType*)malloc(STACK」NIT_SIZE*sizeof(SElemType));if(!s.base)exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_INIT_SIZE;returnOK;1StatusGetTop