利用栈实现迷宫的求解

利用栈实现迷宫的求解

一、要解决的问题：

以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍，设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

二：算法基本思想描述:

用一个字符类型的二维数组表示迷宫，数组中每个元素取值“0”（表示通路）或“1”（表示墙壁）。二维数组的第0行、第m+1行、第0列、第m+1列元素全置成“1”， 表示迷宫的边界；第1行第1列元素和第m行第n列元素置成“0”， 表示迷宫的入口和出口

走迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按东、南、西、北4个方向顺序试探下一个位置；

用二维数组move记录4个方向上行下标增量和列下标增量，则沿第i个方向前进一步，可能到达的新位置坐标可利用move数组确定： Px=x+move[i][0] Py=y+move[i][1]

如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索； 如果4个方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。

三：设计：

1：数据结构的设计：

（1）定义三元数组元素的结构 typedef struct MazeDirect {

int Dx; //行标 int Dy; //列标

int direct; //走到下一个坐标点的方向 }MazeDirect;

（2）定义链表节点的结构组成 typedef struct LinkNode {

elemtype data; //数据域 struct LinkNode *next; //指针域 }LinkNode;

（3）定义链栈的头指针 typedef struct {

LinkNode *top; //栈的头指针 }LinkStack;

（4）移动数组结构的定义 typedef struct {

int x,y;//x为行标，y为列标 }Direction_increm; 2：算法的设计：

【1】迷宫图的设计 设迷宫为m行n列，利用maze[m][n]来表示一个迷宫，maze[i][j]=0或1; 其中：0表示通路，1表示不通，当从某点向下试探时，中间点有4个方向可以试探，（见图）而四个角点有2个方向，其它边缘点有3个方向，为使问题简单化我们用maze[m+2][n+2]来表示迷宫，而迷宫的四周的值全部为1。这样做使问题简单了，每个点的试探方向全部为4，不用再判断当前点的试探方向有几个，同时与迷宫周围是墙壁这一实际问题相一致。 假设有6行8列的迷宫，如下图为maze[8][10]构造的迷宫

1 1 1 1 1 1 1 1 1 1

1 0 1 1 1 0 1 1 1 1

1 0 0 1 0 1 1 1 1 1

1 0 0 0 0 0 0 0 1 1

1 0 0 1 1 0 1 1 1 1

1 1 0 0 0 1 0 0 0 1

1 0 1 1 0 0 0 1 0 1

1 1 1 1 1 1 1 1 1 1

【2】试探方向的设计：

在上述表示迷宫的情况下，每个点有4个方向去试探，如当前点的坐标(x , y)，与其相邻的4个点的坐标都可根据与该点的相邻方位而得到，如图2所示。因为出口在（m，n），因此试探顺序规定为：从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题，方便的求出新点的坐标，将从正东开始沿顺时针进行的这4个方向（用0，1，2，3表示东、南、西、北）的坐标增量放在一个结构数组move [ 4 ]中，在move 数组中，每个元素有两个域组成，x：横坐标增量，y：纵坐标增量。Move数组如图3所示。move数组定义如下：

typedef struct {

int x ; //行 int y ; //列 } item ; item move[4] ;

这样对move的设计会很方便地求出从某点 (x，y) 按某一方向 v (0≤v≤3) 到达的新点（i，j）的坐标：i =x + move[v].x ，j = y + move[v].y 。

(x-1，y)

x y

0 0 1

，y-1) (x

(x，y)

(x，y+1)

1 2 3

(x+1，y)

图2 与点(x，y)相邻的4个点及坐标

1 0 -1 0 -1 0 图3 增量数组move

【3】栈的设计：

当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向，即每走一步栈中记下的内容为(行，列，来的方向)。对于图1所示迷宫，依次入栈为：

栈中每一组数据是所到达的每点的坐标及从该点沿哪个方向向下走的，对于图3迷宫，走的路线为：(1,1,0)(2,1,1)(2,2,0)(3,2,1)(3,3,0)(3,4,0)（下脚标表示方向），当无路可走，则应回溯，对应的操作是出栈，沿下一个方向即方向继续试探。

栈中元素是一个由行、列、方向组成的三元组，栈元素的设计如下： typedef struct{

int x , y , d ;/* 横纵坐标及方向*/ }datatype ;

栈的定义为： SeqStack s ;

top —>

3,4,0 3,3,0 3,2,1 2,2,0 2,1,1 1,1,0 【4】. 如何防止重复到达某点，以避免发生死循环：

一种方法是另外设置一个标志数组mark[m][n]，它的所有元素都初始化为0，一旦到达了某一点 ( i , j )之后，使mark[ i ][ j ] 置1，下次再试探这个位置时就不能再走了。另一种方法是当到达某点（i , j）后使maze[ i ][ j ] 置 -1，以便区别未到达过的点，同样也能起到防止走重复点的目的，此处采用后一方法，算法结束前可恢复原迷宫。

四：详细设计；

1. 算法的设计思想及流程图

（1）主要函数的功能说明

void ini_stack(LinkStack *)/*初始化链栈*/ int empty_Stack(LinkStack *)/*判断是否为空栈*/ void push_Stack(LinkStack *,elemtype)/*入栈*/ elemtype pop_Stack(LinkStack *) /*出栈*/

int size_stack(LinkStack ) /*栈的规模大小*/ （2）算法描述【伪代码描述】

迷宫求解算法思想如下：

(1) 栈初始化;

(2) 将入口点坐标及到达该点的方向（设为-1）入栈 (3) while (栈不空)

{ 栈顶元素＝＞（x , y , d） 出栈 ;

求出下一个要试探的方向d++ ;//当遇到死路的时候就出栈，寻找原来点的下

一个方向

while （还有剩余试探方向时） { if （d方向可走）

则 { （x , y , d）入栈 ; 求新点坐标 (i, j ) ;

将新点（i , j）切换为当前点（x , y） ; if ( (x ,ｙ)= =(ｍ,n) ) 结束 ; else 重置 d=0 ; }

else d++ ; }

}

五：源程序清单；

#include #include int m,n;

typedef struct MazeDirect {

int Dx; int Dy; int direct;

}MazeDirect; /*定义三元数组元素的结构*/

typedef MazeDirect elemtype;

typedef struct LinkNode {

elemtype data;

struct LinkNode *next; /*定义链表节点的结构组成*/ }LinkNode;

typedef struct {

LinkNode *top; /*定义链栈的头指针*/ }LinkStack;

void ini_stack(LinkStack *stack)/*初始化链栈*/ {

stack->top=NULL; }

int empty_Stack(LinkStack *stack)/*判断是否为空栈*/ {

if (stack->top!=NULL) return 0; else

return 1; }

void push_Stack(LinkStack *stack,elemtype x)/*入栈*/ {

LinkNode *s;

s=(LinkNode *)malloc(sizeof(LinkNode));

s->data=x;

s->next=stack->top;

stack->top=s; }

elemtype pop_Stack(LinkStack *stack) /*出栈*/ {

elemtype x; LinkNode *p;

elemtype tmpNull={0,0,0}; if (stack->top==NULL) {

return tmpNull;//(NULL) } else {

x=stack->top->data; p=stack->top;

stack->top=p->next; free(p); return (x); } }

int size_stack(LinkStack stack) /*栈的规模大小*/ {

int i;

LinkNode *Numb; i=0;

Numb=stack.top;

while(Numb!=NULL) {

Numb=Numb->next; i++; }

return i; }

int w,t,maze[100][100];

typedef struct {

int x,y;//x为行标，y为列标

}Direction_increm;

Direction_increm MazeMove[4]={{0,1},{1,0}, {0,-1},{-1,0}};

typedef MazeDirect TmpType;

int Maze_path() {

MazeDirect tmp,path; LinkStack s;

int x,y,Px,Py,d,flag=0; ini_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 (d<4) {

Px=x+MazeMove[d].x; Py=y+MazeMove[d].y; if (maze[Px][Py]==0) {

tmp.Dx=x; tmp.Dy=y; tmp.direct=d;

push_Stack(&s,tmp);

x=Px;y=Py;maze[x][y]=-1;/*标记，防止重复点*/ if(x==m&&y==n) {

flag=1;

printf(\"\\n到达迷宫出口：%d,%d\

printf(\"\\n经过的节点有：%d个\ while(!empty_Stack(&s)) {

path=pop_Stack(&s);

printf(\"\\n(%d,%d,%d)\ }

break; }

else d=0; }//结束if else d++; }//结束内部while }//结束外部while return flag; }

void main() {

printf(\"请输入迷宫图的行数和列数(输入格式为 i,j):\\n\"); scanf(\"%d,%d\ printf(\"创建迷宫图:\\n\"); for(w=0;wfor(t=0;tscanf(\"%d\ getchar();} }

printf(\"\\n找到迷宫的路径（yes/1,no/0）：%d\ getch(); }

运行结果：