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

using?namespace?std;


//class:MazePos-----------------------------------------
//迷宮通道塊類(lèi)型
class?MazePos{
public:
	int?wxly;?//塊的XY坐標(biāo)?
	int?path;?//塊的類(lèi)型;0:空塊-1:墻壁1:出口路徑
	bool?pass;?//是否曾經(jīng)過(guò)（對(duì)墻壁無(wú)意義）;false:沒(méi)有true:曾經(jīng)過(guò)
	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-----------------------------------------
//輔助棧元素類(lèi)型
class?SElemType{
public:
	int?ord;?//迷宮通道塊路徑上的序號(hào)
	MazePos?seat;??//通道塊在迷宮中的位置坐標(biāo)
	int?di;??//從此通道塊走向下一通道塊的方向
????//0:無(wú)效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{
?//由通道塊矩陣構(gòu)成
	MazePos?mazemap[MAPWIDTH][MAPHEIGHT];
}MazeMap;
//End:MazeMap---------------------------------------


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


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

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

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

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

				//封裝棧元素將當(dāng)前位置進(jìn)棧
				SElemType?e;
				e.ord?=curstep;
				e.seat?=curpos;
				e.di?=1;
				mstack.push?（e）;


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