#include?
#include?
#include?
#include?
#include?
#include?
#include?

using?namespace?std;


//class:MazePos-----------------------------------------
//迷宮通道塊類型
class?MazePos{
public:
	int?wxly;?//塊的XY坐標?
	int?path;?//塊的類型;0:空塊-1:墻壁1:出口路徑
	bool?pass;?//是否曾經過（對墻壁無意義）;false:沒有true:曾經過
	bool?operator==（const?MazePos?pos）
	{
		return?（wx==pos.wx?&&?ly==pos.ly?）;
	};
	MazePos?operator=（const?MazePos?pos）
	{
??
		wx=pos.wx;
		ly=pos.ly;
		pass=pos.pass;
		path=pos.path;
		return?*this;
	};
};
//End:MazePos---------------------------------------


//class:SElemType-----------------------------------------
//輔助棧元素類型
class?SElemType{
public:
	int?ord;?//迷宮通道塊路徑上的序號
	MazePos?seat;??//通道塊在迷宮中的位置坐標
	int?di;??//從此通道塊走向下一通道塊的方向
????//0:無效1:東2:南3:西4:北
	bool?operator==（const?SElemType?et）
	{
		return?（seat==et.seat）;?
	};
	SElemType?operator=（const?SElemType?et）
	{
		ord?=et.ord?;
		seat?=et.seat?;
		di?=et.di?;
		return?（*this）;
	};
};
//End:SElemType--------------------------------------


//struct:MazeMap-------------------------------------
//由通道塊組成的迷宮地圖
#define?MAPWIDTH?10
#define?MAPHEIGHT?10

typedef?struct?MazeMap{
?//由通道塊矩陣構成
	MazePos?mazemap[MAPWIDTH][MAPHEIGHT];
}MazeMap;
//End:MazeMap---------------------------------------


//struct::MazeWay----------------------------------------
//輔助出口路徑鏈表元素類型
typedef?struct?MazeWay{
	int?wxly;
}MazeWay;
//End:MazeWay--------------------------------------------


//Class:Maze----------------------------------------
//主體類迷宮路徑問題求解
class?Maze{
public:
	Maze（int?width=MAPWIDTHint?height=MAPHEIGHT）;?//生成迷宮地圖
	~Maze（）;
	void?DoMaze（）;?//找出出口路徑并顯示
private:
	bool?InitOK;?//初始化成功標志
	MazeMap?map;?//迷宮地圖
	MazePos?startend;?//迷宮的入口和出口
	bool?FindPath（）;?//主要函數尋找出口路徑
	list?mazeway;?//存放出口路徑的臨時鏈表
	void?RandMap（）;?//隨機生成迷宮地圖函數
	bool?CreateMap（bool?init）;?//在初始和找到出口路徑后生成相應地圖函數
	bool?pass（MazePos?curpos）;?//當前路徑通道塊是否可通（即是不是未經過的空塊）
	MazePos?NextPos（MazePos?curposint?di）;?//取得當前通道塊當前方向上的下一個通道塊
	bool?Invalide（SElemType?e）;?//使當前通道塊標記為不可通
	void?DisplayMaze（）;?//顯示迷宮地圖
};

Maze::Maze（int?widthint?height）{
?//
?//隨機生成迷宮地圖
	CreateMap（true）;
?//顯示地圖
	DisplayMaze（）;
}

Maze::~Maze（）{
?//Add?codes?here
}

bool?Maze::FindPath?（）{
?//
?//尋找出口并生成出口路徑鏈表
	if（InitOK）
	{
??//MazeStack?mstack;
		stack?>?mstack;
		MazePos?curpos=start;?
		int?curstep=1;?//經過的步數
		MazeWay?mw;?//出口路徑塊元素
		unsigned?mwsize=mazeway.size?（）;?//為顯示運行過程而設
		do
		{
			if（pass（curpos））
			{
				//如果當前位置可通（即是未走過的空塊）

				//封裝棧元素將當前位置進棧
				SElemType?e;
				e.ord?=curstep;
				e.seat?=curpos;
				e.di?=1;
				mstack.push?（e）;


				//保存當前位置到出口路徑鏈表
				mw.wx?=e.seat?.wx?;
				mw.ly?=e.seat?.ly?;
				mazeway.push_back?（mw）;
				//如果是出口則結束
				if（curpos==end）
					return?true;
				//不然就將得到下一個通道塊
				curpos=NextPos（curpose.di?）;