#include<iostream.h>
int m=3;
int n=3;
int mg[4][4];
int zx[3],zy[3];
typedef struct node{
    int data[2];
    int data1[3];
    struct node *next;
}SNode;
class Lstack{
public:
    SNode *top;
    Lstack()
    {
    top->data[0]=1;
    top->data[1]=1;
    top->data1[0]=1;
    top->data1[1]=1;
    top->data1[2]=1;
    top->next=NULL;
    }
    void push(SNode *&p);
//    SNode* pop(Lstack &);
    void mgsf();
    friend disp(Lstack &);

};

void Lstack::push(SNode * &p)
{
    p->next=top;
    top=p;
}
/*(SNode* Lstack::pop(Lstack &L2)
{
    SNode *p=new SNode;
    SNode *q=new SNode;
    if(L2.top!=NULL)
    {
      p->data[0]=L2.top->data[0];
      p->data[1]=L2.top->data[1];
      p->data1[0]=L2.top->data1[0];
      p->data1[1]=L2.top->data1[1];
      p->data1[2]=L2.top->data1[2];
      p->next=NULL;
      q=top;
      top=top->next;
      delete q;
    }
    return p;
}*/
void Lstack::mgsf()
{
    int i,j,k,x,y,find;
    SNode *p=new SNode;
    find=1;
    mg[1][1]=-1;
    while(find)
    {
        x=top->data[0];y=top->data[1];
        for(k=0;k<=3;k++)
        {
            i=x+zx[k];j=y+zy[k];
            if(mg[i][j]==0)
            {
                p->data[0]=i;
                p->data[1]=j;
                p->next=NULL;
                mg[i][j]=-1;
            }
            if(zx[k]==-1)
            {
                p->data1[2]=0;
            }
            if(zy[k]==-1)
            {
                p->data1[2]=3;
            }
            if(zx[k]==1)
            {
                p->data1[0]=top->data1[0]+1;
                p->data1[2]=1;
            }
            if(zy[k]==1)
            {
                p->data1[1]=top->data1[1]+1;
                p->data1[2]=2;
            }
            push(p);
            if(i==m && j==n)
            {
                find=1;
            }
        }
    }
}
 disp(Lstack & L1)
{
    cout<<"结果为："<<endl;
    SNode *p,*q;
    while(L1.top)
    {
        if(L1.top!=NULL)
    {
      p->data[0]=L1.top->data[0];
      p->data[1]=L1.top->data[1];
      p->data1[0]=L1.top->data1[0];
      p->data1[1]=L1.top->data1[1];
      p->data1[2]=L1.top->data1[2];
      p->next=NULL;
      q=L1.top;
      L1.top=L1.top->next;
      delete q;
    }
        cout<<"("<<p->data[0]<<","<<p->data[1]<<",";
        if(p->data1[2]==0)
        {cout<<p->data1[1]<<")";}
        if(p->data1[2]==1)
        {cout<<p->data1[0]<<")";}
        else if(p->data1[2]==2)
            {cout<<L1.top->data1[1]<<")";}
        else 
        {cout<<p->data1[0]<<")";}
        cout<<"  ";
    }
}

void main()
{
    int i,j;
    cout<<"请输入迷宫矩阵："<<endl;
    for(i=1;i<=m;i++)
    {for(j=1;j<=n;j++)
     cin>>mg[i][j];
    // cout<<endl;
    }
      
    for(i=0;i<m+1;i++)
    {
        mg[i][0]=1;mg[i][n+1]=1;
    }
    for(j=0;j<m+1;j++)
    {
        mg[j][0]=1;mg[j][m+1]=1;
    }
    zx[0]=-1;zx[1]=0;zx[2]=0;zx[3]=1;
    zy[0]=0;zy[1]=-1;zy[2]=1;zy[3]=0;
    Lstack L1;
    L1.mgsf();
    disp(L1);

}