#include
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]={{01}{10}{0-1}{-10}};???//定義當前位置移動的4個方向
bool?Mazepath（int?**mazeint?mint?n）;//尋找迷宮maze中從（0，0）到（mn）的路徑?????
?????//到則返回true否則返回false
void?PrintPath（Stack?p）;????????//輸出迷宮的路徑
void?Restore（int?**mazeint?mint?n）;????????//恢復迷宮
int**?GetMaze（int?&mint?&n）;???????//獲取迷宮
?????????????????????????????????//返回存取迷宮的二維指針
int?main（）
{
	int?m=0n=0;???????//定義迷宮的長和寬
????int?**maze;????????//定義二維指針存取迷宮
????maze=GetMaze（mn）;??//調用GetMaze（int?&mint?&n）函數，得到迷宮
????if（Mazepath（mazemn））?//調用Mazepath（int?**mazeint?mint?n）函數獲取路徑
????cout<<“迷宮路徑探索成功!\n“;
????else?cout<<“路徑不存在!\n“;
????return?0;
}

int**?GetMaze（int?&mint?&n）//返回存取迷宮的二維指針
{
	int?**maze;??????????????//定義二維指針存取迷宮
????int?i=0j=0;
????cout<<“請輸入迷宮的長和寬:“;
????int?ab;cin>>a>>b;?????????????//輸入迷宮的長和寬
????cout<<“請輸入迷宮內容:\n“;
????m=a;
????n=b;??????????//mn分別代表迷宮的行數和列數
????maze=new?int?*[m+2];??//申請長度等于行數加2的二級指針
????for（i=?0;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		maze[i][0]=maze[i][n+1]=1;
????for（i=0;i		maze[0][i]=maze[m+1][i]=1;
????return?maze;??????????????//返回存貯迷宮的二維指針maze
};

bool?Mazepath（int?**mazeint?mint?n）//尋找迷宮maze中從（0，0）到（mn）的路徑
???????????//到則返回true否則返回false
{
	Stack?q