#include<iostream>
using namespace std;
class T       //定義描述迷宮中當前位置的結構類型
{
public:
	int x;          //x代表當前位置的行坐標
	int y;          //y代表當前位置的列坐標
	int dir;        //0:無效,1:東,2:南,3:西,4:北
};
class LinkNode      //鏈表結點
{
	friend class Stack;
public:
	T data;
	LinkNode *next;
};
class Stack
{
private:
 LinkNode *top;           //指向第一個結點的棧頂指針
public:
 Stack();              //構造函數，置空棧
 ~Stack();             //析構函數
 void Push(T e);           //把元素data壓入棧中
 T Pop();                  //使棧頂元素出棧
 T GetPop();               //取出棧頂元素
 void Clear();                   //把棧清空
 bool empty();        //判斷棧是否為空，如果為空則返回1，否則返回0
};
Stack::Stack()          //構造函數，置空棧
{
 top=NULL;
}
Stack::~Stack()         //析構函數
{
}
void Stack::Push(T e)          //把元素x壓入棧中
{
 LinkNode *P;
 P=new LinkNode;
 P->data=e;
 P->next=top;
 top=P;
}
T Stack::Pop()                 //使棧頂元素出棧
{
	T Temp;
	LinkNode *P;
	P=top;
	top=top->next;
	Temp=P->data;
	delete P;
	return Temp;
}
T Stack::GetPop()               //取出棧頂元素
{
	return top->data;
}
void Stack::Clear()                    //把棧清空
{
 top=NULL;
}
bool Stack::empty()        //判斷棧是否為空，如果為空則返回1，否則返回0
{
 if(top==NULL) return 1;
 else return 0;
}
int move[4][2]={{0,1},{1,0},{0,-1},{-1,0}};   //定義當前位置移動的4個方向
bool Mazepath(int **maze,int m,int n);      
     //尋找迷宮maze中從（0，0）到（m,n）的路徑
     //到則返回true,否則返回false
void PrintPath(Stack p);        //輸出迷宮的路徑
void Restore(int **maze,int m,int n);        //恢復迷宮
int** GetMaze(int &m,int &n);       //獲取迷宮
                                 //返回存取迷宮的二維指針
int main()
{
 int m=0,n=0;       //定義迷宮的長和寬
 int **maze;        //定義二維指針存取迷宮
 maze=GetMaze(m,n);  //調用GetMaze(int &m,int &n)函數，得到迷宮
 if(Mazepath(maze,m,n)) //調用Mazepath(int **maze,int m,int n)函數獲取路徑
  cout<<"迷宮路徑探索成功!\n";
 else cout<<"路徑不存在!\n";
 return 0;
}
int** GetMaze(int &m,int &n)//返回存取迷宮的二維指針
{
	int **maze;              //定義二維指針存取迷宮
	int i=0,j=0;
	cout<<"請輸入迷宮的長和寬:";
	int a,b;cin>>a>>b;             //輸入迷宮的長和寬
	cout<<"請輸入迷宮內容:\n";
	m=a;
	n=b;          //m,n分別代表迷宮的行數和列數
	maze=new int *[m+2];  //申請長度等于行數加2的二級指針
	for(i= 0;i<m+2;i++)  //申請每個二維指針的空間
	{
		maze[i]=new int[n+2];
	}
	for(i=1;i<=m;i++)          //輸入迷宮的內容，1代表可通，0代表不通
		for(j=1;j<=n;j++)
			cin>>maze[i][j];
		for(i=0;i<m+2;i++)
			maze[i][0]=maze[i][n+1]=1;
		for(i=0;i<n+2;i++)
			maze[0][i]=maze[m+1][i]=1;
		return maze;              //返回存貯迷宮的二維指針maze
};
bool Mazepath(int **maze,int m,int n)//尋找迷宮maze中從（0，0）到（m,n）的路徑
           //到則返回true,否則返回false
{
 Stack q,p;       //定義棧p、q,分別存探索迷宮的過程和存儲路徑
 T Temp1,Temp2;      
 int x,y,loop;
 Temp1.x=1;
 Temp1.y=1;
 q.Push(Temp1);           //將入口位置入棧
 p.Push(Temp1);
 maze[1][1]=-1;          //標志入口位置已到達過
 while(!q.empty())      //棧q非空，則反復探索
 {
  Temp2=q.GetPop();      //獲取棧頂元素
  if(!(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y)) 
   p.Push(Temp2);         
     //如果有新位置入棧，則把上一個探索的位置存入棧p
  for(loop=0;loop<4;loop++)   //探索當前位置的4個相鄰位置
  {
   x=Temp2.x+move[loop][0];     //計算出新位置x位置值
   y=Temp2.y+move[loop][1];      //計算出新位置y位置值
   if(maze[x][y]==0)         //判斷新位置是否可達
   {
    Temp1.x=x;
    Temp1.y=y;
    maze[x][y]=-1;          //標志新位置已到達過
    q.Push(Temp1);         //新位置入棧
   }
   if((x==(m))&&(y==(n)))    //成功到達出口
   {
    Temp1.x=m;
    Temp1.y=n;
    Temp1.dir=0;
    p.Push(Temp1);       //把最后一個位置入棧
    PrintPath(p);        //輸出路徑
    Restore(maze,m,n);        //恢復路徑
    return 1;            //表示成功找到路徑
   }
  }
  if(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y)
        //如果沒有新位置入棧，則返回到上一個位置
  {
   p.Pop();
   q.Pop();
  }
 }
 return 0;           //表示查找失敗，即迷宮無路經
}
void PrintPath(Stack p)        //輸出路徑
{
 cout<<"迷宮的路徑為\n";
 cout<<"括號內的內容分別表示為(行坐標,列坐標,數字化方向,方向)\n";
 Stack t;            //定義一個棧，按從入口到出口存取路徑
 int a,b;
 T data;
 LinkNode *temp;
 temp=new LinkNode;         //申請空間
 temp->data=p.Pop();        //取棧p的頂點元素，即第一個位置
 t.Push(temp->data);  //第一個位置入棧t
 delete temp;         //釋放空間
 while(!p.empty())    //棧p非空，則反復轉移
 {
  temp=new LinkNode;
  temp->data=p.Pop();         //獲取下一個位置
  //得到行走方向
  a=t.GetPop().x-temp->data.x;   //行坐標方向
  b=t.GetPop().y-temp->data.y;   //列坐標方向
  if(a==1) temp->data.dir=1;     //方向向下，用1表示
  else if(b==1) temp->data.dir=2; //方向向右，用2表示
  else if(a==-1) temp->data.dir=3;  //方向向上，用3表示
  else if(b==-1) temp->data.dir=4;  //方向向左，用4表示
  t.Push(temp->data);            //把新位置入棧
  delete temp;
 }
 //輸出路徑，包括行坐標，列坐標，下一個位置方向
 while(!t.empty())         //棧非空，繼續輸出
 {
  data=t.Pop();
  cout<<'('<<data.x<<','<<data.y<<','<<data.dir<<",";  //輸出行坐標，列坐標
  switch(data.dir)   //輸出相應的方向 
  {
  case 1:cout<<"↓)\n";break;
  case 2:cout<<"→)\n";break;
  case 3:cout<<"↑)\n";break;
  case 4:cout<<"←)\n";break;
  case 0:cout<<")\n";break;
  }
 }
}
void Restore(int **maze,int m,int n)       //恢復迷宮
{
 int i,j;
 for(i=0;i<m+2;i++)            //遍歷指針
  for(j=0;j<n+2;j++)       
  {
   if(maze[i][j]==-1)         //恢復探索過位置，即把-1恢復為0
    maze[i][j]=0;
  }
}