#include <stdio.h>
#include <conio.h>
#include <alloc.h>
struct stack {
  int x,y,pos;
} *p,tmp;

struct offset {
 int x,y;
};

struct offset move[8]=
  { {-1,0}, {-1,1}, {0,1}, {1,1},
    {1,0} , {1,-1}, {0,-1},{-1,-1}
  };

int top;
char mark[9][7]={ 63*0 };
char aa[9][7]={
   1,1,1,0,1,0,0,
   1,1,0,1,0,1,1,
   0,0,1,1,1,1,1,
   1,0,0,1,0,1,0,
   1,1,1,0,1,0,1,
   1,1,1,0,0,1,1,
   1,1,0,0,0,1,1,
   1,1,0,1,1,1,1,
   0,0,0,1,1,1,1,
};

void push(int x,int y,int dir)
{
  (p+top)->x=x; (p+top)->y=y; (p+top)->pos=dir; top++;
}

void pop()
{
 top--; if (top < 0) { printf("no way out is dead end\n"); exit(1); }
 tmp.x= (p+top)->x;  tmp.y= (p+top)->y;  tmp.pos= (p+top)->pos;
}

void main()
{
  int x,y,tx,ty,td,i,j,n;
  char pa,*tpa;

  printf("give me the number --> "); scanf("%d",&n);
  p=(struct stack *)malloc(sizeof(struct stack)*n); top=0;

  x=8; y=0; td=0; mark[x][y]=1;
  while ((x != 0) || (y != 6)) { /* the final position  */
    while (td < 8) { /* td is the position */
      tx=x+move[td].x; ty=y+move[td].y;
      if ((tx >= 0) && (tx <= 8) && (ty >= 0) && (ty <= 6)) {/* in the maze */
        if ((aa[tx][ty] == 0) && (mark[tx][ty] == 0)) {/* can go,no one been*/
	  mark[tx][ty]=1; push(x,y,td);
	  printf("push (%d,%d,%d) --\n",x,y,td); getchar();
	  x=tx; y=ty; td=0;
	  break;
	} /* if the move legal */
	else td++;
      } /* if legal position checking */
      else td++;
    } /* while 8 position */
    if (td == 8) { /* no way out, cannot check if the maze is dead */
      pop(); x=tmp.x; y=tmp.y; td=tmp.pos;
      printf("pop (%d,%d,%d) --\n",x,y,td); getchar();
    }
    printf("process (%d,%d,%d)\n",x,y,td); getchar();
  } /* while */

  printf("the reverse path -->\n");
  push(0,6,td);
  while (top > 0) {
    pop();
    printf("x=%d y=%d dir=%d\n",tmp.x,tmp.y,tmp.pos);
  }
}