走迷宫算法

#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 ）;