#include<stdlib.h>
#include<stdio.h>
 struct  postype 
{int x;
int y;
} begin,end;
typedef struct postype posit;
#define MAXLENGTH 100
typedef int  mazetype[MAXLENGTH][MAXLENGTH];
mazetype m;

int x,y,i,j;
 print()
{int i,j;
for(i=0;i<x;i++)
{for(j=0;j<y;j++)
printf("%3d",m[i][j]);
printf("\n");
}}
void init(int k)
{int i,j,x1,y1;
printf("請輸入迷宮的行數和列數：");
scanf("%d,%d",&x,&y);

for(i=0;i<x;i++)
{m[0][i]=0;
m[x-1][1]=0;}

for(i=0;i<y-1;i++)
{m[i][0]=0;
m[i][y-1]=0;}
for(i=1;i<x-1;i++)
for(j=1;j<y-1;j++)
m[i][j]=k;
printf("請個數輸入迷宮內墻的個數:\n");
scanf("%d",&j);
printf("請依次輸入內墻的行數和列數:\n");
for(i=1;i<=j;i++)
{scanf("%d,%d",&x1,&y1);
m[x1][y1]=0;
}
printf("迷宮的結構如下:\n");
print();
printf("請輸入迷宮的入口的行數和列數:");
scanf("%d,%d",&begin.x,&begin.y);
printf("請輸入迷宮的出口的行數和列數：");
scanf("%d,%d",&end.x,&end.y);}

 extern int curstep=1;
  struct eltype
{int ord;
posit seat;
int di;
};
 typedef  struct eltype quzzle;
 pass(posit b)
{if(m[b.x][b.y]==1)
return 1;
 else return 0;}


footprint(posit a)
{m[a.x][a.y]=curstep;/*使迷宮的M的A點的值變為足跡*/
}
posit nextpos(posit c,int di)
{posit direc[4]={{0,1},{1,0},{0,-1},{-1,0}};/*移動的方向，依次為東南西北*/
c.x+=direc[di].x;
c.y+=direc[di].y;
return c;
}
markprint(posit b)
{m[b.x][b.y]=-1;}/*把迷宮的B點變為-1（表示不能通過的路徑）*/
quzzle s[MAXLENGTH];
int top=-1;
posit curpos;
quzzle e;

mazepath(posit start,posit end)
{/*若迷宮中有從入口到出口的路徑，則求出放在棧中，并返回TURE；否則則返回FALSE*/
quzzle s[MAXLENGTH];
int top=-1;
posit curpos;
quzzle e;


curpos=start;curstep=1;
do{
	if (pass(curpos)){
footprint(curpos);
e.ord=curstep;
e.seat=curpos;
e.di=0;
if(top>=MAXLENGTH)
{printf("棧的內容已滿\n");
return -1;}
top++;
s[top]=e;
curstep++;
if(curpos.x==end.x&&curpos.y==end.y)
return 1;
    nextpos(curpos,e.di);}
else
{if(top!=-1)
{	 if(top<0)
{printf("棧的內容是空的\n");
return -1;}

top--;
curstep--;
while(e.di==3)
{markprint(e.seat);
	 if(top<0)
{printf("棧的內容是空的\n");
return -1;}

top--;
curstep--;
}   
if(e.di<3)
{e.di++;
if(top>=MAXLENGTH)
{printf("棧的內容已滿\n");
return -1;}
top++;
s[top]=e;
curstep++;
curpos=e.seat;
nextpos(curpos,e.di);
}}}}
while(top!=-1);
return 0;}

main()
{init(1);
if(mazepath(begin,end))
{print();
}
else printf("no path\n");
}