#include <iostream.h>
#include <malloc.h>
#include <conio.h>
#define MAXSIZE 100
typedef struct  {
    int x,y,d;
}DataType;
//typedef  DataType DataType;
typedef struct  {
    DataType data[MAXSIZE];
    int top;
}SeqStack;
const int M = 50; //最大列数
const int N = 50;
int maze[M][N]; int m,n;
typedef struct{
    int x;
    int y;
}item;
item move[8]={(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1),(-1,0),(-1,1)};
//置空栈
SeqStack *Init_SeqStack(){
    SeqStack *s=new SeqStack;
    if (!s){
        cout<<"空间不足"<<endl;
        return NULL;
    }
    else{
        s->top=-1;
        return s;
    }
};
//判栈空
int Empty_SeqStack(SeqStack *s){
    if (s->top==-1)
        return 1;
    else
        return 0;
    
}
//入栈
int Push_SeqStack(SeqStack *s,DataType x){
    if(s->top==MAXSIZE-1)
        return 0;
    else{
        s->top++;
        s->data[s->top]=x;
        return 1;
    }
}
//出栈
int Pop_SeqStack(SeqStack *s,DataType *x){
    if(Empty_SeqStack(s))
        return 0;
    else{
        *x=s->data[s->top];
        s->top--;
        return 1;
    }
}
//////////////////////

//////////////////////
void printpath(SeqStack *s){
    for(int i=0;i<s->top;i++)
    {
        cout<<"("<<s->data[i].x<<","<<s->data[i].y<<")->";
    }
    cout<<"("<<s->data[s->top].x<<","<<s->data[s->top].y<<")"<<endl;
}
int path(int maze[][],item move[8]){
    SeqStack *s=Init_SeqStack();
    DataType temp;
    int x,y,d,i,j;
    temp.x=1;
    temp.y=1;
    temp.d=-1;
    Push_SeqStack(s,temp);
    while(!Empty_SeqStack(s)){
        Pop_SeqStack(s,&temp);
        x=temp.x;
        y=temp.y;
        d=temp.d+1;
        while(d<8){
            i=x+move[d].x;
            j=y+move[d].y;
            if (maze[i][j]==0){
                temp.x=x;
                temp.y=y;
                temp.d=d;
                Push_SeqStack(s,temp);
                x=i;
                y=j;
                maze[x][y]=-1;
                if(x==m&&y==n){
                    temp.x=x;
                    temp.y=y;
                    temp.d=-1;
                    Push_SeqStack(s,temp);
                    printpath(s);
                    return 1;
                }
                else
                    d=0;
            }
            else
                d++;
        }
    }
    
    return 0;
}
void main()
{    

 
int i,j;
 
cout<<"请输入迷宫的行跟列(x,y):";
cin>>m>>n; /*输入迷宫的行和列*/

cout<<"请输入迷宫\n"; /*输入迷宫,1代表路障,0代表通行*/
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
cin>>maze[i][j];
for(i=0;i<n+2;i++) /*将迷宫的四周都变为1*/
maze[0][i]=1;
for(i=0;i<n+2;i++)
maze[m+1][i]=1;
for(i=0;i<m+2;i++)
maze[i][0]=1;
for(i=0;i<m+2;i++)
maze[i][n+1]=1;
for(i=0;i<m+2;i++) /*输出迷宫*/
{
for(j=0;j<n+2;j++)
cout<<maze[i][j];
cout<<"\n";
}
 
    cout<<"路径："<<endl;
    path(maze[][],move[]);
}