#include<stdio.h>
#define MAXSIZE 100
typedef struct           //迷宫中y行x列的位置
{                       

         int y;

         int x;

}PostType;
typedef struct
{

         int ord;      //当前位置在路径上的序号

         PostType seat;//当前坐标

         int di;       //往下一坐标的方向  0-右 1-上 2-左 3-下 4-无路可走

         int flog;     //迷宫内位置的属性 0-围墙 1-路 2-起点 3-终点
         
         int sign;     //标记以前走过的路  1-走过 0-没走过
}SElemType;
typedef struct
{
  SElemType  maze[10][10];
  SElemType  stack[MAXSIZE];
  int top;
}maze;
SElemType *q;
Initial( maze *p )                //初始化
{
  int i,j;

  for(i=0;i<=9;i++)         //设置外围墙
  {
    for(j=0;j<=9;j++)           //给每一个格子写上坐标
    {
      p->maze[i][j].seat.y=i;
      p->maze[i][j].seat.x=j;
    }
    p->maze[0][i].flog=0;       //第1行
    p->maze[9][i].flog=0;       //第九行
    p->maze[i][0].flog=0;       //第一列
    p->maze[i][9].flog=0;       //第九列   
    switch(i)               //设置内围墙
    {
      case 1: p->maze[8][i].flog=0;  break;
      case 2:
      {      
        p->maze[4][i].flog=0;
        p->maze[6][i].flog=0;
          p->maze[7][i].flog=0;
        break;    
      }
      case 3:
      {     
        p->maze[1][i].flog=0;
        p->maze[2][i].flog=0;
        p->maze[4][i].flog=0;
        p->maze[7][i].flog=0;
        break;
      }
      case 4:
      {
        p->maze[4][i].flog=0;
        p->maze[5][i].flog=0;
        p->maze[7][i].flog=0;
        break;
      }
      case 5:
      {
        p->maze[3][i].flog=0;
        break;
      }
        case 6:
      {
        p->maze[3][i].flog=0;
        p->maze[6][i].flog=0;
        p->maze[7][i].flog=0;
        break;
      }
      case 7:
      {
        p->maze[1][i].flog=0;
        p->maze[2][i].flog=0;
        p->maze[7][i].flog=0;
        break;
      }
    }
  }  
  p->maze[1][1].flog=3;           //设置起点
  p->maze[8][8].flog=4;           //设置终点
  p->top=-1;                      //栈的初始化
}

int test( maze *p )
{
  if(p->maze[q->seat.y][q->seat.x+1].flog!=0 && p->maze[q->seat.y][q->seat.x+1].sign!=1)
  {     
    return(0);  //右边能走
  }
  else if(p->maze[q->seat.y-1][q->seat.x].flog!=0 && p->maze[q->seat.y-1][q->seat.x].sign!=1)
  {
    return(1);  //上能走
  }
  else if(p->maze[q->seat.y][q->seat.x-1].flog!=0 && p->maze[q->seat.y][q->seat.x-1].sign!=1)
  {
    return(2);  //左边能走
  }
  else if(p->maze[q->seat.y+1][q->seat.x].flog!=0 && p->maze[q->seat.y+1][q->seat.x].sign!=1)
  {
    return(3);  //下能走
  }
  else return(4);       //走到了尽头
}


back( maze *p )
{
  printf("%d,%d\n",q->seat.y,q->seat.x); /**********************************/
  p->top--;
  if(p->maze[q->seat.y][q->seat.x+1].ord==q->ord-1)  //如果右边是上次走过的路
  {
    q->ord=-1;           //取消现在这个位置在栈内的序号
    q=&p->maze[q->seat.y][q->seat.x+1];            //让q指向右
  }
  else if(p->maze[q->seat.y-1][q->seat.x].ord==q->ord-1)  //如果上边是上次走过的路
  {
    q->ord=-1;           //取消现在这个位置在栈内的序号
    q=&(p->maze[q->seat.y-1][q->seat.x]);            //让q指向上
  }
  else if(p->maze[q->seat.y][q->seat.x-1].ord==q->ord-1)  //如果左边是上次走过的路
  {
    q->ord=-1;           //取消现在这个位置在栈内的序号
    q=&(p->maze[q->seat.y][q->seat.x-1]);            //让q指向左
  }
  else if(p->maze[q->seat.y+1][q->seat.x].ord==q->ord-1)  //如果下边是上次走过的路
  {
    q->ord=-1;           //取消现在这个位置在栈内的序号
    q=&(p->maze[q->seat.y+1][q->seat.x]);            //让q指向下
  }
      q->di=test( p );    // 0-右 1-上 2-左 3-下
      switch(q->di)        //让q指向下一个
      {
    case 0:           //让q指向右
    {
      q=&p->maze[q->seat.y][q->seat.x+1];
      break;
    }
    case 1:          //让q指向上
    {
      q=&p->maze[q->seat.y-1][q->seat.x];
      break;
    }
    case 2:           //让q指向左
    {
      q=&p->maze[q->seat.y][q->seat.x-1];
      break;
    }
    case 3:           //让q指向下
    {
      q=&p->maze[q->seat.y+1][q->seat.x];
      break;
    }
    case 4:
    {
      back( p );
    }
  }
}

go( maze *p)
{
    printf("%d,%d\n",q->seat.y,q->seat.x); /**********************************/
    
    p->top++;
    p->stack[p->top]=*q;
    q->sign=1;            //对走过的路做记号
    q->ord=p->top;        //对位置在栈内的顺序进行编号
    if(q->flog==4)        //到达终点
    {
      exit(0);
    }else                //还要再走
    {
      q->di=test( p );    // 0-右 1-上 2-左 3-下     
      switch(q->di)        //让q指向下一个
      {
        case 0:           //让q指向右
        {
          q=&p->maze[q->seat.y][q->seat.x+1];
          break;
        }
        case 1:          //让q指向上
        {
          q=&p->maze[q->seat.y-1][q->seat.x];
          break;
        }
        case 2:           //让q指向左
        {
          q=&p->maze[q->seat.y][q->seat.x-1];
          break;
        }
        case 3:           //让q指向下
        {
          q=&p->maze[q->seat.y+1][q->seat.x];
          break;
        }
        case 4:
        {
          back( p );
        }
      }     
    }
}          
        
main()
{
  maze *p;
  
  p=(maze *)malloc(sizeof(maze));
  
  Initial( p );
  q=&p->maze[1][1];           //手动的让q指向起点     
  go( p );
  while(p->top>=0)
  {
    go( p );
  }    
}