#include

#define?N?5

int?m[N][N]?=?{
	{00111}
	{01001}
	{11110}
	{01000}
	{11111}
};

//標(biāo)志數(shù)組
bool?flag[N][N];

typedef?struct?position
{
	int?row;
	int?col;
}POSITION;

typedef?struct?node
{
	POSITION?pos;
	struct?node*?pNext;
}NODE*PNODE;

class?Stack
{
private:
	PNODE?pBottom;
	PNODE?pTop;
	
public:
	Stack（）
	{
		pBottom?=?pTop?=?new?NODE;
		pBottom->pNext?=?NULL;
	}
	
	void?Push（POSITION?pos）
	{
		PNODE?pNew?=?new?NODE;
		pNew->pos?=?pos;
		pNew->pNext?=?pTop;
		
		pTop?=?pNew;
	}
	
	bool?IsNULL（）
	{
		if（pBottom?==?pTop）
			return?true;
		else
			return?false;
	}
	
	POSITION?Pop（）
	{
		POSITION?pos?=?pTop->pos;
		
		PNODE?p?=?pTop;
		pTop?=?pTop->pNext;
		delete?p;
		
		return?pos;
	}
	
	void?Clear（）
	{
		while（!IsNULL（））
		{
			Pop（）;
		}
	}
	
	void?Print（）
	{
		PNODE?p?=?pTop;
		
		while（p?!=?pBottom）
		{
			cout<pos.row<<“?“<pos.col<			p?=?p->pNext;
		}
	}
	
	//返回棧頂元素
	POSITION?GetTop（）
	{
		return?pTop->pos;
	}
	
	~Stack（）
	{
		Clear（）;
		delete?pBottom;
	}
};

void?InitFlag（）
{
	for（int?i=0;i	{
		for（int?j=0;j		{
			flag[i][j]?=?false;
		}
	}
}

void?Migong（POSITION?pos_beginPOSITION?pos_end）
{
	Stack?st;//棧
	POSITION?pos_cur;//當(dāng)前位置
	POSITION?pos_new;//新位置
	bool?IsFind;//判斷是否找到合法新位置
	
	InitFlag（）;//初始化標(biāo)記數(shù)組
	
	st.Push（pos_begin）;//走到出發(fā)點(diǎn)
	flag[pos_begin.row][pos_begin.col]?=?true;//設(shè)置已經(jīng)走過(guò)標(biāo)志
	
	while（!st.IsNULL（）?
		&&?
		（st.GetTop（）.row?!=?pos_end.row?||?st.GetTop（）.col?!=?pos_end.col））
	{	
		pos_cur?=?st.GetTop（）;//獲得當(dāng)前位置
		
		IsFind?=?false;
		
		for（int?i=0;i<4;i++）//查找4個(gè)方向
		{
			if（i==0）//0?方向
			{
				pos_new.row?=?pos_cur.row;
				pos_new.col?=?pos_cur.col-1;
				
			}
			else?if（i?==?1）//1?方向
			{
				pos_new.row?=?pos_cur.row+1;
				pos_new.col?=?pos_cur.col;
			}
			else?if（i?==?2）
			{
				pos_new.row?=?pos_cur.row;
				pos_new.col?=?pos_cur.col+1;
			}
			else
			{
				pos_new.row?=?pos_cur.row-1;
				pos_new.col?=?pos_cur.col;
			}
			
			
			if（（pos_new.row>=0?&&?pos_new.row<=4?&&pos_new.col>=0?&&?pos_new.col<=4）//不越界
				&&
				flag[pos_new.row][pos_new.col]?==?false//沒(méi)走過(guò)
				&&
				m[pos_new.row][pos_new.col]?==?1//是通路
				）
			{
				IsFind?=?true;//設(shè)置找到合法新位置的標(biāo)志
				break;
			}
		}
		
		if（IsFind）
		{
			st.Push（pos_new）;
			flag[pos_new.row][pos_new.col]?=?true;
		}
		else
		{
			st.Pop（）;
		}
	}

	if（st.IsNULL（））//未找到出路
	{
		cout<<“迷宮是死的，沒(méi)有出路!!!“<	}
	else
	{
		cout<<“找到一條出路：“<		st.Print（）;
	}
}

void?main（）
{
	POSITION?pos_begin;
	POSITION?pos_end;

	pos_begin.row?=?4;
	pos_begin.col?=?0;

	pos_end.row?=?0;
	pos_end.col?=?4;


	Migong（pos_beginpos_end）;

}

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----

?????文件???????2923??2005-01-04?13:07??maze.cpp

-----------?---------??----------?-----??----

?????????????????2923????????????????????1