//回遡法的迷宮求解：
#include<iostream.h>

struct node
{
  int x;
  int y;
};
 struct stack
{
  node kk[100];
  int top;
};

int stackempty(stack L);
void hahapop(stack &L);
void push(stack &L,int i,int j);
int stackempty(stack L);
void pop(stack &L);

int  digui(int m[][4],stack &L,int i,int j)
{
  if(m[i][j]==3)
  {
   cout<<"終于找到了："<<endl;
   hahapop(L);
   return 0;
  }
  else if( m[i][++j]==0&&i<4&&j<4&&i>=0&&j>=0)
     {
       push(L,i,j);
       digui(m,L,i,j);
     }
  else if(m[++i][--j]==0&&i<4&&j<4&&i>=0&&j>=0)
     {
       push(L,i,j);
       digui(m,L,i,j);
     }
  else if(m[--i][--j]==0&&i<4&&j<4&&i>=0&&j>=0)
     {
       push(L,i,j);
        digui(m,L,i,j);
     }
  else if(m[--i][++j]==0&&i<4&&j<4&&i>=0&&j>=0)
     {
       push(L,i,j);
       digui(m,L,i,j);
     }
  else if(i!=0&&j!=0&&i<4&&j<4&&i>=0&&j>=0)
       {
        m[++i][j]=1;
        pop(L);
        digui(m,L,i,j);
       }
  else
  {
   cout<<"完了，沒出路"<<endl;
  return -1;
  }
  return 1;
}
void hahapop(stack &L)
{ 
  cout<<"它的路徑是"<<endl;
  while(!stackempty(L))
  {
   pop(L);
  }
}
void push(stack &L,int i,int j)
{
  L.kk[L.top].x=i;
  L.kk[L.top++].y=j;
}
void pop(stack &L)
{
  cout<<L.kk[L.top].x<<" "<<L.kk[L.top--].y<<endl;
}
int stackempty(stack L)
{
if(L.top==0)
return 1;
else 
return 0;
}
void main()
{
  stack L;
  L.top=1;
  int m[4][4]={0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,3};
  digui(m,L,0,0);
  hahapop(L);
}