#include
#include
#include
#define?MAXSIZE?100
using?namespace?std;
int?sign[MAXSIZE][MAXSIZE];//標記矩陣，當相應塊走過后，值變為1
typedef?struct
{
	int?x;
	int?y;
}PosType;

typedef?struct
{
	int?ord;
????PosType?seat;
	int?di;
}SElemType;

typedef?struct
{
	int?m;
	int?n;
	int?map[MAXSIZE][MAXSIZE];
}MazeType;

class?Stack
{
public:
	SElemType?data[MAXSIZE];
	int?top;
	Stack（void）
	{
		top=-1;
	}
	void?push（SElemType?e）
	{
		top++;
		data[top].ord=e.ord;
		data[top].di=e.di;
		data[top].seat=e.seat;
	}
	void?pop（SElemType?&e）
	{
		e.di=data[top].di;
		e.ord=data[top].ord;
		e.seat=data[top].seat;
		top--;
	}
	int?empty（）
	{
		if（top==-1）
			return?1;
		else
			return?0;
	}

};

void?FootPrint（PosType?ps）
{
	sign[ps.x][ps.y]=1;
}

int?Pass（MazeType?mazemapPosType?ps）
{
	if（mazemap.map[ps.x][ps.y]==0&&sign[ps.x][ps.y]==0）
		return?1;
	else?
		return?0;
}

PosType?NextPos（PosType?psint?di）
{
	PosType?temp;
	switch（di）
	{
	case?1:
		temp.x=ps.x+1;
		temp.y=ps.y;
		break;
	case?2:
		temp.x=ps.x;
		temp.y=ps.y-1;
		break;
	case?3:
		temp.x=ps.x-1;
		temp.y=ps.y;
		break;
	case?4:
		temp.x=ps.x;
		temp.y=ps.y+1;
		break;
	}
	return?temp;
}
int?MazePath（MazeType??&mazemapPosType?startPosType?end）
{
	Stack?st;
	SElemType?e;
	PosType?curpos=start;
	int?curstep=1;
	for（int?i=0;i		for（int?j=0;j			sign[i][j]=0;
	do
	{
		if（Pass（mazemapcurpos））
		{
			FootPrint（curpos）;
			e.ord=curstep;
			e.seat=curpos;
			e.di=1;
			st.push（e）;
			if（curpos.x==end.x&&curpos.y==end.y）
			{
				for（int?i=0;i<=st.top;i++）
				{
					mazemap.map[st.data[i].seat.x][st.data[i].seat.y]=3;
				//	cout<<“（“<				}
				return?1;
			}
			curpos=NextPos（curpos1）;
			curstep++;
		}
		else
		{
			if（!st.empty（））
			{
				st.pop（e）;
				while（e.di==4&&!st.empty（））
				{
					FootPrint（e.seat）;
					st.pop（e）;
				}
				if（e.di<4）
				{
					e.di++;
					st.push（e）;
	//				cout<<“（“<<（e.seat）.x<<““<<（e.seat）.y<<“）“<					curpos=NextPos（e.seate.di）;
				}
			}
		}

	}while（!st.empty（））;
	return?0;
}

void?printmaze（MazeType?mazemapPosType?startPosType?end）
{
	for（int?i=0;i	{
		cout<<“\t\t“;
		for（int?j=0;j		{			
			if（1==mazemap.map[i][j]）
				cout<<“墻“;
			else?if（i==start.x&&j==start.y）
				cout<<“口“;
			else?if（i==end.x&&j==end.y）
				cout<<“口“;
			else?if（3==mazemap.map[i][j]）
				cout<<“口“;
			else?
				cout<<“??“;
		}
		cout<	}
}

void?usermaze（）
{
	MazeType?usermap;
	PosType?m_startm_end;
	cout<<“輸入迷宮寬度:“<	cin>>usermap.n;
	cout<<“輸入迷宮高度:“<	cin>>usermap.m;	
	for（int?i=0;i	{
		cout<<“輸入第“<		for（int?j=0;j		{
			cin>>usermap.map[i][j];
		}
	}
	cout<<“輸入迷宮入口橫坐標:“<	cin>>m_start

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????6056??2008-12-31?15:04??數據結構作業\maze.cpp

?????文件?????160768??2009-01-02?18:21??數據結構作業\實習報告.doc

?????目錄??????????0??2008-12-31?16:27??數據結構作業

?????文件?????565327??2008-12-31?15:04??數據結構作業\maze.exe

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

???????????????732151????????????????????4