#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;
}
}