迷宫求解 原创 C书写
typedef struct{
int X,Y; //表示点的方位
int Live; //Live=1,该点可走，Live=0,该点不可走
int direction=10; //direction 表示当前点探索的方向,direction 初始10表示该点未探索任何方向
int count=1; //count表示当前点探索方向次数
}Frame frame[M*N];
typedef struct
{
int self; //self表示点的探索方向North，South，West，East
int next;
}MoveDirection MD[4];
Status InitMoveDirection(MD) //North=0,South=1,West=2,East=3
{
for(k=0;k<=2;k++)
{
MD[k].self=k;
MD[k].next=k+1;
}
MD[3].self=3;
MD[3].next=0;
return ok;
}
int Transform(int Gone) //转变方向
{
if(Gone%2==0) return Gone+1;
else return Gone-1;
}
int Number(int x,int y,int self) //计算点编号
{
switch (self)
{
case 0: return N*(y-1)+x;
case 1: return N*(y+1)+x;
case 2: return N*y+x-1;
case 3: return N*y+x+1;
}
}
Status Answer(Stack s) //输出路径编号
{
Stack q;
Pop(s,e);
Push(q,e);
printf("Path Below:\n\t");
while( !StackEmpty(q) )
{
Pop(q,e);
printf(e);
}
DestroyStack(q);
return ok;
}
Status MazePath() //求解M*N的迷宫
{
k=2;
InitStack(s);
Push(s,N+1);
while( !StackEmpty(s) )
{
GetTop(s,cur);
while( frame[cur].count<=3)
{
if(cur==Arrival) { Answer(s); return ok; } //Arrival 目的地编号
if( frame[cur].direction!=10 ) k=frame[cur].direction;
m=MD[k].next;
frame[cur].direction=m;
next=Number( frame[cur].X, frame[cur].Y, MD[m].self );
frame[cur].count++;
if( frame[next].Live==1 )
{
Gone=m;
Push(s,next);
break;
}
}
if( frame[cur].count==4 ) Pop(s);
else k=Transform(Gone);
}
printf("No Path");
DestroyStack(s);
return ERROR;
}
算法没有提供迷宫的初始化，即frame【M*N】中变量X，Y，Live的初始
