#include<stdio.h>
#include<stdlib.h>
#define SIS 100/*運行棧一次分配的空間*/
#define N 10/*迷宮的最大坐標，根據迷宮大小修改*/
struct sit/*數據結構定義迷宮坐標*/
{
int seatx;
int seaty;
};
struct finds
{
int ord;/*路徑標號*/
struct sit *seat;
int di;/*下一步試探的方向，上下左右用1，2，3，4來表示*/
};
struct stack/*定義運行棧*/
{
struct finds *base;
struct finds *top;
int size;
};
void initstack(struct stack *s)/*構造運行棧*/
{
struct finds *link,*end;
s->base=s->top=link=(struct finds *)malloc(SIS*sizeof(struct finds));
end=link+SIS-1;
for(;link<=end;link++)
link->seat=(struct sit *)malloc(sizeof(struct sit));
s->size=SIS;
}
void push(struct stack *s,struct finds *find)/*把*find壓入棧s，棧定指針加1*/
{
struct finds *link,*end;
if(s->top-s->base>=s->size)
{
s->base=(struct finds *)realloc(s->base,(s->size+SIS)*sizeof(struct finds));
link=s->base+s->size;
s->top=s->size+s->base;
s->size+=SIS;
end=s->base+s->size;
for(;link<=end;link++)
link->seat=(struct sit *)malloc(sizeof(struct sit));

}
s->top->ord=find->ord;
s->top->seat->seatx=find->seat->seatx;
s->top->seat->seaty=find->seat->seaty;
s->top->di=find->di;
s->top++;
}
void pop(struct stack *s,struct finds *find)/*棧頂元素*find出棧*/
{
s->top--;
find->ord=s->top->ord;
find->seat->seatx=s->top->seat->seatx;
find->seat->seaty=s->top->seat->seaty;
find->di=s->top->di;
}
void footprint(int a[N][N],struct sit *seat)/*走過的路經留下足跡，也就是將坐標值為非零*/
{
int i,j;
i=seat->seatx;
j=seat->seaty;
a[i][j]=-1;
}
void nextpos(struct sit *find,struct sit *seat,int di)/*規定下一步試探的方向*/
{
int i,j;
switch(di)
{case 1:i=seat->seatx;j=seat->seaty+1;break;
case 2:i=seat->seatx+1;j=seat->seaty;break;
case 3:i=seat->seatx;j=seat->seaty-1;break;
case 4:i=seat->seatx-1;j=seat->seaty;break;
}
find->seatx=i;
find->seaty=j;
}
int pass(struct sit *curpos,int a[N][N])/*判斷改足跡是否走過，走過為1否則為0，進行下一步試探*/
{
int i,j;
i=curpos->seatx;
j=curpos->seaty;
if(a[i][j]==0)return 1;
else return 0;
}

print(struct stack *s)/*輸出結果，輸出結果不太好看，但這不是程序的關鍵部分，你可以自己修改輸出方法*/
{ do
{
printf("(%d,%d)",s->base->seat->seatx,s->base->seat->seaty);
s->base++;
}while(s->top!=s->base);
}
void main()
{
struct stack *s;
struct finds *find,*e;
struct sit *start,*end,*curpos;
int curstep=1,a[N][N],i,j,n,m,pa;
char c[N][N];
s=(struct stack *)malloc(sizeof(struct stack));
find=(struct finds *)malloc(sizeof(struct finds));
e=(struct finds *)malloc(sizeof(struct finds));
start=(struct sit *)malloc(sizeof(struct sit));
end=(struct sit *)malloc(sizeof(struct sit));
curpos=(struct sit *)malloc(sizeof(struct sit));
initstack(s);
puts("在使用前請仔細閱讀使用說明");
while(1)
{
printf("請輸入迷宮的長和寬（n，m）");
pa=scanf("%d,%d",&n,&m);
if(pa!=2||n>81||m>81||n<=0||m<=0)puts("輸入數據錯誤,請重新輸入");
else break;
}

printf("請輸入你的迷宮（0代表路徑,連續輸入）\n");
for(i=0;i<n;i++)
scanf("%s",c[i]);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
a[i][j]=c[i][j]-48;
while(1)
{
printf("進入迷宮的位置（n，m）");
scanf("%d,%d",&curpos->seatx,&curpos->seaty);
if(curpos->seatx>81||curpos->seaty>81||curpos->seatx<=0||curpos->seaty<=0||curpos->seatx>=n||curpos->seatx>=m||curpos->seaty>=m||curpos->seaty>=n)puts("輸入數據錯誤,請重新輸入");
else break;

}
while(1)
{
printf("走出迷宮的位置（n，m）");
scanf("%d,%d",&end->seatx,&end->seaty);
if(end->seatx>81||end->seaty>81||end->seatx<=0||end->seaty<=0||end->seatx>=n||end->seatx>=m||end->seaty>=n||end->seaty>=m)puts("輸入數據錯誤,請重新輸入");
else break;
}

do
{
if(pass(curpos,a))
{footprint(a,curpos);
e->ord=curstep;
e->seat=curpos;
e->di=1;
push(s,e);
if(curpos->seatx==end->seatx&&curpos->seaty==end->seaty)break;
nextpos(curpos,e->seat,1);
curstep++;
} 
else {
if(e->di<4){pop(s,e);e->di++,push(s,e);nextpos(curpos,e->seat,e->di);}
else if(e->di==4)
{
pop(s,e);pop(s,e);push(s,e);e->di++;
if(e->di>4)pop(s,e);
nextpos(curpos,e->seat,e->di);
}
}

}while(1);
puts("輸出路徑為");
print(s);
puts("\n");

}