typedef     struct   StackNode
{
    ElemType    data;
    StackNode   *next;
)StackNode, *LinkType;                      //结点类型，指针类型



typedef    struct
{
    LinkType    top;
    int    size;
}Stack;                                     //栈类型





//栈的基本操作如下

Status   InitStack(Stack  &s)
{
    s.top=NULL;
    s.size=0;
    return ok;
}





Status     Push(Stack  &s,ElemType  e)
{
    p=(LinkType*)malloc( sizeof(StackNode) );
    if(!p)      return FALSE;
    p.data=e;
    p.next=s.top;
    s.top=p;
    s.size++;
    return TURE;
}







Status      StackEmpty(Stack &s)
{
    if(s.top==NULL)     return TURE;
    else    return FALSE;
}










Status    GetTop(Stack &s,ElemType e)
{
    if( s.top==NULL )   return  ERROR;
    e=s.top->data;
    return  OK;
}








Status    Pop(Stack  &s)
{
    if( s.top==NULL )   return  ERROR;
    p=s.top;
    s.top=p->next;
    s.size--;
    free(p);
    return  OK;
}






Status   DestroyStack(Stack &s)
{
    free(s);
    return Ok;
}

//栈的基本操作如上







//迷宫类型

typedef    struct
{

    int   x,y;                           //表示点的方位
    int   Live;                         //Live=1,该点可走，Live=0,该点不可走，Live=2表示该点是解
    int   direction=10;                 //direction 表示当前点探索的方向,direction 初始10表示该点未探索任何方向
    int   count=1;                      //count表示当前点探索方向次数

}MazeType    maze[M*N];


//迷宫基本操作如下

status    InitMaze(MazeType &maze)                             //初始化迷宫,为方便操作,迷宫外设了一圈围墙
{
    for(j=0;j<=N-1;j++)
    {
        maze[j].Live=0;
        maze[j].x=j;
        maze[j].y=0;
        maze[ (M-1)*N+j ].Live=0;
        maze[ (M-1)*N+j ].x=j;
        maze[ (M-1)*N+j ].y=M-1;
    }
    for(i=1;i<=M-2;i++)
    {
        maze[i*N].Live=0;
        maze[i*N].x=0;
        maze[i*N].y=i;
        maze[ i*N+N-1 ].Live=0;
        maze[ i*N+N-1 ].x=N-1;
        maze[ i*N+N-1 ].y=i;
    )                                                                //初始化围墙部分
    printf("Input Maze:0 stand for unclear,1 stand for clear\n");
    for(i=1;i<=M-2;i++)
        for(j=1;j<=N-2;j++)
        {
            maze[ N*i+j ].x=j;
            maze[ N*i+j ].y=i;
            scanf( maze[ N*i+j ].Live );                               //用户输入迷宫部分
        }
    if(maze[N+1].Live==0)
    {
        maze[N+1].Live=1;
        printf("Sorry,(1,1)must be initialized alive");
    }
    return ok;
}







Status   MazeSolve(MazeType &maze)                             //求解M*N的迷宫
{
    k=2;
    InitStack(s);
    Push(s,N+1);
    while( !StackEmpty(s) )
    {
        GetTop(s,cur);
        while( maze[cur].count<=3)
        {
            if(cur==Arrival)   {   Answer(maze,s);     return ok;  }              //Arrival 目的地编号
            if( maze[cur].direction!=10 )      k=maze[cur].direction;
            m=MD[k].next;
            maze[cur].direction=m;
            next_number=Number( maze[cur].x, maze[cur].y, m);
            maze[cur].count++;
            if( maze[next_number].Live==1 )
            {
                Gone=m;
                Push(s,next_number);
                break;
            }
        }
        if( maze[cur].count==4 )      Pop(s);
        else    k=Transform(Gone);
    }
    printf("No Path");
    DestroyStack(s);
    return  ERROR;
}



Status  Answer( MazeType &maze,Stack s )                        // 确定最终路径,更新Live值
{
    while( !StackEmpty(s) )
    {
         Pop(s,e);
         maze[e].Live=2;
    }
    DestroyStack(s);
    return ok;
}





Status   Print( MazeType &maze )                             //打印结果
{
    count=0;
    k=1;
    while(count<=M*N-1)
    {
        switch( maze[count].Live )
        {                                                     //0代表不通,1代表通,*代表路径
            case 0: printf("0");
            case 1: printf("1");
            case 2: printf("*");
        }
        if( k%N==0 )   printf("\n");
        k++;
    }
    return OK;
}

//迷宫基本操作如上









//方向类型

typedef    struct
{

    int    next;

}MoveDirection    MD[4];




//方向的基本操作如下

Status    InitMoveDirection(&MD)               //North=0,South=1,West=2,East=3
{
    for(k=0;k<=2;k++)
    {
        MD[k].next=k+1;
    }
    MD[3].next=0;
    return ok;
}





int    Transform(int Gone)                      //Gone表示来的方向
{                                               //函数的功能是返回与Gone相反的方向
    if( Gone%2==0 )   return  Gone+1;
    else    return  Gone-1;
}

//方向的基本操作如上










int    Number(int x,int y,int direction)              //根据移动方向和当前点位置确定下个点编号
{
    switch (direction)
    {
        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;
    }
}










#define M=10;
#define N=10;
int    main()
{
      MazeType   maze[M*N];
      InitMaze(maze);
      printf("Maze Below:");
      Print(maze);
      MazeSolve(maze);
      printf("Maze Sovled Below:");
      Print(maze);
      return 0;
}