迷宫求解--使用栈

        迷宫求解是数据结构中一个经典的程序设计题，一般情况下采用的式穷举求解的方法，即从迷宫的入口出发，沿着某一方向前进，若能走通则继续前进，若不通需原 路退回后改变方向继续前进，直到找到出口为止，为了保证在任何位置都可以原路退回，自然使用“栈”就是很自然的了。

寻找迷宫 路径的算法如下：

do{
        若 当前位置可通，
        则{
                将 当前位置压入栈顶； /*纳入路径*/
                若当前位置是出口位 置，则结束；/*求得的路径已在栈中*/
                否则切换当前位置的东临块为新的当前位置；
                }
        否 则
                {
                        若栈不空，且栈顶位置尚有其它方向未搜索，
                                则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下 一临块；
                        若栈不空但栈顶位置四周均不可通，
                        则
                        {
                                删去栈顶位置；
                                若栈不空，则重新测试新的栈顶位置，直到找到一个可通的相 邻块或出栈至栈空；
                                }
                        }
        }while(站不空);

以上图所示 的迷宫为例，我们使用栈来寻找迷宫路径：

/********************main.c***********************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "MazePath.c"
int main()
{
int m[11][11] = {
{1,1,1,1,1,1,1,1,1,1,1},
{1,0,1,1,0,0,0,1,0,0,1},
{1,0,0,0,1,0,1,0,0,1,1},
{1,0,1,1,1,0,1,1,0,0,1},
{1,0,0,0,0,0,0,0,1,0,1},
{1,1,1,0,1,0,1,0,0,0,1},
{1,0,0,0,1,0,1,0,1,0,1},
{1,1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,0,0,0,1,1,0,1},
{1,1,0,1,1,0,1,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1}
};
MazeType maze = {m,11,11};
PosType start = {1,1},end = {9,9};
if(MazePath(maze,start,end))
{
printf("\nSuccessfully Find Way Out!\n");
return 0;
}
else
{
printf("No Way Out!\n");
return 0;
}
}





/*******************************************/

/**************MazePath.c*************/

#define MAXSIZE 1024
#define footed -1
#define marked -2
#define East 1
#define South 2
#define West 3
#define North 4
#define True 1
#define False 0
typedef int STATUS;
typedef int DirType;
typedef int BOOL;
typedef struct
{
void *ptr;
int colum;
int row;
}MazeType;
typedef struct
{
int x;
int y;
}PosType;
typedef struct
{
PosType seat;
DirType di;
}StackElement;
typedef struct
{
StackElement *base;
StackElement *top;
int size;
}Stack;

int InitStack(Stack *stp)
{
stp->top = stp->base = (StackElement*)malloc(sizeof(StackElement)*(stp->size));
if(stp->top)return 0;
else printf("Stack Initialized Error!\n");
return 1;
}

int PushStack(Stack *stp,StackElement *sep)
{
if(stp->top-stp->base == stp->size-1)
{
printf("Stack is Full!\n");
return 1;
}
*(stp->top) = *sep;
stp->top++;
return 0;
}

int PopStack(Stack *stp,StackElement *sep)
{
if(stp->base == stp->top)
{
printf("Stack is Empty");
return 1;
}
stp->top--;
*sep = *(stp->top);
return 0;
}

int IsStackEmpty(Stack *stp)
{
if(stp->top == stp->base)return 1;
else return 0;
}

int GetTop(Stack *stp,StackElement *sep)
{
if(stp->top == stp->base)
{
printf("Stack is Empty!\n");
return 1;
}
else *sep = *(stp->top-1);
return 0;
}

void DispPos(PosType pos)
{
printf("Position: %d %d \n",pos.x,pos.y);
}

void DispPath(Stack *st)
{
StackElement *sep;
sep = st->base;
printf("The Path is as following:\n");
while(sep < st->top)
{
printf("(%d,%d)",(sep->seat).x,(sep->seat).y);
if(sep!=st->top-1)printf("-->");
sep++;
}
}

PosType NextPos(PosType pos,DirType dir)
{
switch(dir)
{
case East:
pos.y++;
return pos;
case South:
pos.x++;
return pos;
case West:
pos.y--;
return pos;
case North:
pos.x--;
return pos;
default:
return pos;
}
}

STATUS MazePath(MazeType maze,PosType start,PosType end)
{
int m[maze.row][maze.colum];
int i=0,j=0;
memcpy(m,maze.ptr,sizeof(int)*(maze.row)*(maze.colum));
/*for(i=0;i{
for(j=0;j{
printf("%d ",m[i][j]);
}*/ /*打印传入的迷宫*/
printf("\n");
}
Stack st;
st.size = MAXSIZE;
InitStack(&st);
StackElement se;
PosType curpos = start;
DispPos(curpos);
do{
if(m[curpos.x][curpos.y] == 0)
{
m[curpos.x][curpos.y] = footed;
se.seat = curpos;
se.di = East;
PushStack(&st,&se);
if((curpos.x == end.x)&&(curpos.y == end.y))
{
printf("\nSuccessfully arrived at Exit!\n");
DispPath(&st);
return True;
}
curpos = NextPos(curpos,se.di);
DispPos(curpos);
}
else
{
if(!IsStackEmpty(&st))
{
PopStack(&st,&se);
}
while((se.di ==4)&&!IsStackEmpty(&st))
{
m[curpos.x][curpos.y] = marked;
PopStack(&st,&se);
}
if(se.di < 4)
{
se.di++;
PushStack(&st,&se);
curpos = NextPos(se.seat,se.di);
DispPos(curpos);
}
}
}while(!IsStackEmpty(&st));
return False;
}




/*******************************************/

编译后，运行输出以下结果：
Position: 1  1
Position: 1  2
Position: 2  1
Position: 2  2
Position: 2  3
Position: 2  4
Position: 3  3
Position: 2  2
Position: 1  3
Position: 3  2
Position: 2  1
Position: 1  2
Position: 3  1
Position: 3  2
Position: 4  1
Position: 4  2
Position: 4  3
Position: 4  4
Position: 4  5
Position: 4  6
Position: 4  7
Position: 4  8
Position: 5  7
Position: 5  8
Position: 5  9
Position: 5  10
Position: 6  9
Position: 6  10
Position: 7  9
Position: 7  10
Position: 8  9
Position: 8  10
Position: 9  9

Successfully arrived at Exit!
The Path is as following:
(1,1)-->(2,1)-->(3,1)-->(4,1)-->(4,2)-->(4,3)-->(4,4)-->(4,5)-->(4,6)-->(4,7)-->(5,7)-->(5,8)-->(5,9)-->(6,9)-->(7,9)-->(8,9)-->(9,9)
Successfully Find Way Out!

可以看到寻找到的路径为：(1,1)-->(2,1)-->(3,1)--> (4,1)-->(4,2)-->(4,3)-->(4,4)-->(4,5)-->(4,6)-->(4,7)-->(5,7)-->(5,8)-->(5,9)-->(6,9)-->(7,9)-->(8,9)-->(9,9)