#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）的路徑
???????????/