迷宫求解 原创 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的初始