#include "stdio.h"
#include "stdlib.h"
#include "process.h"
#define N 10

typedef struct lnode                               /*定義結(jié)構(gòu)體*/
{
int x;
int y;
int d;
    struct lnode *next;
}lnode,*link;                       

typedef struct                                   /*定義堆棧*/
{
link base;
link top;
}*stack;                          

stack creat()                              /*堆棧分配空間*/
{
stack s;
s->base=(link)malloc(sizeof(lnode));        /*利用malloc函數(shù)分配空間*/


if(s->base==NULL)                             /*堆棧滿*/
{
  printf("Overflow");
  exit(0);
}
s->base->x=50;                                  /*給base分配空間*/
s->base->y=50;
s->base->d=50;
s->base->next=NULL;
s->top=s->base;
return s;
}                                              

stack push(stack s,int r,int c,int D)              /*進(jìn)棧*/
{                                                  
link p;                                              /*定義p并分配空間*/
p=(link)malloc(sizeof(lnode));
p->x=r;                                                /*給棧中的x,y,z的data賦值*/
p->y=c;
p->d=D;
p->next=s->top;
s->top=p;

return s;
}                                                                  

stack pop(stack s)
{
link p;
if(s->top==s->base)
{
  printf("It's empty.\nthere is no access to enter.\n");
  exit(0);
}
p=s->top;
s->top=s->top->next;
free(p);
return s;
}


stack found(stack s,int a[N][N],int b[4][2])
{
int r=1,c=1,D=0,i=0,D0=0,f=0;
while(r!=8|c!=9)
{
  if(a[r][c]==0)
  {
   if(f)                           /*當(dāng)不能沿棧頂結(jié)點(diǎn)所指的方向走時(shí),f為真*/
    s->top->d=D;
   D0=(D+2)%4;                     /*D0為準(zhǔn)備退回時(shí)的方向*/
   D=0;                       /*指該元素指向下一個(gè)元素的方向*/

   s=push(s,r,c,D);
   a[s->top->x][s->top->y]=5;      /*入棧的元素，對(duì)應(yīng)的數(shù)組元素做相應(yīng)的改變*/
   f=0;
   if(D==D0)
   {
    D=D+1;
    f=1;
   }
  }
  else
  {
   f=1;
   D=D+1;
   if(D==D0)
   {
    D=D+1;
   }

   if(D>3)
   {
    a[s->top->x][s->top->y]=2;     /*出棧的元素，對(duì)應(yīng)數(shù)組元素做相應(yīng)的改變*/
    s=pop(s);
    D=s->top->next->d;
    D0=(D+2)%4;

   }
  }
  for(i=0;i<4;i++)
                if(i==D)                  /*根椐D的方向來確定下一結(jié)點(diǎn)的坐標(biāo)*/
  {
   r=s->top->x+b[i][0];
   c=s->top->y+b[i][1];
   break;
  }
}
if(s->top!=s->base)                                  /*棧非空則輸出*/
  printf("success to find!\n");
else
  printf("No access to go out\n");
return s;

}

void print(int a[N][N])
{
int i,j;
for(i=0;i<N;i++)
{
  for(j=0;j<N;j++)
   printf("%3d",a[i][j]);
  printf("\n\n");
}
}

void main()
{
stack s;
int a[N][N]={
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,1,1,1,0,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,1,1,1,1,1,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}};
int b[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
s=creat();
printf("the map is:\n");
print(a);
printf("please enter to find\n");
getch();
s=found(s,a,b);
printf("the result map is:\n");
print(a);
getch();
}