#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;
}
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個方向
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;
}
}
int**?GetMaze(int?&m,int?&n)//返回存取迷宮的二維指針
{
int?**maze;//定義二維指針存取迷宮
int?i=0,j=0;
cout<<"請輸入迷宮的長和寬:";
int?a,b;cin>>a>>b;//輸入迷宮的長和寬
cout<<"請輸入迷宮內容:(0為通路，1為墻)\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++)//輸入迷宮的內容，0代表可通，1代表不通
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）的路徑
{
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;//表示查找失敗，即迷宮無路經
}
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;
}
輸入數據：
搜索的路徑為：