利用栈实现迷宫的求解

1、利用栈实现迷宫的求解、要解决的问题： 以一个 m*n 的长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍，设计一个 程序，对任意设定的迷宫，求出一条从入口到出口的通路， 或得出没有通路的结 论。二：算法基本思想描述：用一个字符类型的二维数组表示迷宫，数组中每个元素取值“0”（表示通路）或“ 1”（表示墙壁）。二维数组的第 0 行、第 m+1 行、第 0 列、第 m+1 列元素全置成“ 1”，表示 迷宫的边界；第 1 行第 1 列元素和第 m 行第 n 列元素置成“ 0”，表示迷宫的入口和出口走迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按东、南、西、北4 个方向顺序试探下一个位置

2、；用二维数组 move 记录 4 个方向上行下标增量和列下标增量，则沿第 i 个方向前进一步，可能到达的新位置坐标可利用move 数组确定：Px=x+movei0Py=y+movei1如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索； 如果 4 个方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。三：设计：1：数据结构的设计：（1）定义三元数组元素的结构typedef struct MazeDirectint Dx; 行标int Dy; / 列标int direct; /走到下一个坐标点的方向MazeDirect;（2）定义链表节点的结构组成typede

3、f struct Lin kNodeelemtype data;数据域struct Li nkNode *n ext;/ 指针域Li nkNode;（3）定义链栈的头指针typedef structLi nkNode *top;/栈的头指针Li nkStack;（4）移动数组结构的定义typedef structint x,y;/x 为行标，y 为列标Directio n_in crem;2:算法的设计：【1】迷宫图的设计设迷宫为 m 行 n 列，利用 mazemn来表示一个迷宫，mazeij=0 或 1;其中：0 表示通路，1 表示不通，当从某点向下试探时，中间点有4 个方向可以试探，（见图

4、）而四个角点有2个方向，其它边缘点有3 个方向，为使问题简单化我们用mazem+2n+2来表示迷宫，而迷宫的四周的值全部为1。这样做使问题简单了，每个点的试探方向全部为4，不用再判断当前点的试探方向有几个，同时与迷宫周围是墙壁这一实际问题相一致。假设有 6 行 8 列的迷宫，如下图为maze810构造的迷宫【2】试探方向的设计：在上述表示迷宫的情况下，每个点有 4 个方向去试探，如当前点的坐标 （x , y），与其相邻的 4 个点的坐标都可根据与该点的相邻方位而得到，如图2 所示。因为出口在（m，n），因此试探顺序规定为：从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题，方便的求

5、出新点的坐标，将从正东开始沿顺时针进行的这4 个方向（用 0，1, 2，3 表示东、南、西、北）的坐标增量放在一个结构数组move 4 中，在 move 数组中，每个元素有两个域组成，x：横坐标增量，y:纵坐标增量。Move 数组如图 3 所示。move 数组定义如下：typedef struct int x ;/ 行int y ;列 item ;item move4;这样对 move 的设计会很方便地求出从某点（x, y）按某一方向 v （0 v(x , y , d )出栈；求出下一个要试探的方向 d+ ;/当遇到死路的时候就出栈，寻找原来点的下一个方向 while(还有剩余试探方向时) i

6、f( d 方向可走)则(x , y , d )入栈;求新点坐标(i, j );将新点(i , j)切换为当前点(x , y);if ( (x , y )= =( m ,n)结束；else 重置 d=0 ;else d+ ;五：源程序清单；#i nclude #i nclude int m,n;typedef struct MazeDirectint Dx;int Dy;int direct;MazeDirect;/*定义三元数组元素的结构*/typedef MazeDirect elemtype;typedef struct Lin kNodeelemtype data;struct Lin

7、kNode *n ext;/*定义链表节点的结构组成*/Li nkNode;typedef structLi nkNode *top;/*定义链栈的头指针*/Lin kStack;void ini_stack(LinkStack *stack)/* 初始化链栈 */stack-top=NULL;int empty_Stack(LinkStack *stack)/* 判断是否为空栈 */if (stack-top!=NULL)return 0;elsereturn 1;void push_Stack(LinkStack *stack,elemtype x)/* 入栈 */Li nkNode *s

8、;s=(L in kNode *)malloc(sizeof(Li nkNode);s-data=x;s-n ext=stack-top;stack-top=s;elemtype pop_Stack(LinkStack *stack) /* 出栈 */ elemtype x;Lin kNode *p;elemtype tmpNull=0,0,0;if (stack-top=NULL)return tmpNull;/(NULL)else x=stack-top-data; p=stack-top;stack-top=p-n ext; free(p);return (x); int size_st

9、ack(L in kStack stack) int i;Li nkNode *Numb;i=0;Numb=stack.top; while(Numb!=NULL) Numb=Numb-n ext; i+;return i; int w,t,maze100100;typedef structint x,y;/x 为行标，y 为列标Directio nn crem;Directionncrem MazeMove4=0,1,1,0,0,-1,-1,0;typedef MazeDirect TmpType;int Maze_path()MazeDirect tmp,path;Lin kStack s

10、;int x,y,Px,Py,d,flag=O;/*栈的规模大小*/in i_stack (& s);tmp.Dx=1;tmp.Dy=1;tmp.direct=-1;push_Stack (&s,tmp);while (!empty_Stack( &s)tmp=pop_Stack (&s);x=tmp.Dx;y=tmp.Dy;d=tmp.direct+1; 遇到死路的时候，回溯(通过出栈完成)while (d4)Px=x+MazeMoved.x;Py=y+MazeMoved.y;if (mazePxPy=O)tmp.Dx=x;tmp.Dy=y;tmp.direc

11、t=d;push_Stack (&s,tmp);x=Px;y=Py;maze x y=-1;/* 标记，防止重复点 */ if(x=m&y=n)flag=1;printf(n 到达迷宫出口：d,%d,x,y);printf(n 经过的节点有：%d 个,size_stack(s);while(!empty_Stack( &s)path=pop_Stack (&s);prin tf(n(%d,%d,%d),path.Dx,path.Dy,path.direct);break;else d=0;结束 ifelse d+;/结束内部 while/结束外部 whilereturn flag;void mai n()printf(”请输入迷宫图的行数和列数(输入格式为 i,j)