#define?M2?12?/*M2*N2為實際使用迷宮數(shù)組的大小*/
#define?N2?11
#define?maxlen?M2?//?棧長度
#include?
#include
#include?

int?M=M2-2N=N2-2;//M*N迷宮的大小
typedef?struct?//定義棧元素的類型
{
	int?xydir;
}elemtype;

typedef?struct?//??定義順序棧
{
	elemtype?stack?[maxlen];
	int?top;
}sqstktp;

?struct?moved
	?//定義方向位移數(shù)組的元素類型對于存儲坐標(biāo)增量的方向位移數(shù)組move
?{?int?dxdy;};

//////////////////////////////////////////////////////////////

?void?inimaze（int?maze[][N2]）////初始化迷宮
?{
	?int?ijnum;
	?for（i=0j=0;i<=M+1;i++）//設(shè)置迷宮邊界
		maze[i][j]=1;
	?for（i=0j=0;j<=N+1;j++）
		?maze[i][j]=1;
	?for（i=M+1j=0;j<=N+1;j++）
		?maze[i][j]=1;
	?cout<<“原始迷宮為：“<	?for（i=1;i<=M;i++）
	?{
		?for?（j=1;j<=N;j++）
		?{
			?num=（800*（i+j）+1500）?%?327;//根據(jù)MN的值產(chǎn)生迷宮
			?if?（（num<150）&&（i!=M||j!=N））
				?maze[i][j]=1;
			?else?
				?maze[i][j]=0;
			?cout<		?}
		?cout<	?}
	?cout<	?
?}//inimaze

////////////////////////////////////////////////////////////////////////
void?inimove（struct?moved?move[]）//初始化方向位移數(shù)組
{//依次為East，Southeast，south，southwest，west，northwest，north，northeast
	move[0].dx=0;move[0].dy=1;
	move[1].dx=1;move[1].dy=1;
	move[2].dx=1;move[2].dy=0;
	move[3].dx=1;move[3].dy=-1;
	move[4].dx=0;move[4].dy=-1;
	move[5].dx=-1;move[5].dy-=1;
	move[6].dx=-1;move[6].dy=0;
	move[7].dx=-1;move[7].dy=1;
}//

void?inistack（sqstktp?*s）???????/*初始化棧*/
{
	s->top=-1;
}??????????????????????????????/*inistack*/
int?push（sqstktp*selemtype?x）
{
	if（s->top==maxlen-1）
		return（false）;
	else
	{
		s->stack[++s->top]=x;/*棧不滿，執(zhí)行入棧操作*/
		return（true）;
	}
}/*push*/

elemtype?pop（sqstktp?*s）/*棧頂元素出棧*/
{
	elemtype?elem;
	if（s->top<0）?????//如果棧空，返回空值
	{
		elem.x=NULL;
		elem.y=NULL;
		elem.dir=NULL;
		return（elem）;
	}
	else
	{
		s->top--;
		return（s->stack[s->top+1]）;????//棧不空，返回棧頂元素
	}
}??//pop

////////////////////////////////////////////////////////////////////////////////////

void?path（int?maze[][N2]struct?moved?move[]sqstktp?*s）?????//尋找迷宮中的一條通路
{
	int?ijdirxyf;
	elemtype?elem;
	i=1;j=1;dir=0;
	maze[1][1]=-1;???//設(shè)[1][1]為入口處
	do?
	{
		x=i+move[dir].dx;//球下一步可行的到達(dá)點的坐標(biāo)
		y=j+move[dir].dy;
		if（maze[x][y]==0）
		{
			elem.x=i;elem.y=j;elem.dir=dir;
			f=push（selem）;//如果可行將數(shù)據(jù)入棧
			if（f==false）//如果返回假，說明棧容量不足
				cout<<“棧長不足“;
			i=x;j=y;dir=0;maze[x][y]=-1;
		}
		else
			if?（dir?				dir++;
			else
			{
				elem=pop（s）;?????//8個方向都不行，回退
				if（elem.x!=NULL）
				{
					i=elem.x;
					j=elem.y;
					dir=elem.dir+1;
				}
			}
	}while（!（（s->top==-1）&&（dir>=7）||（x==M）&&（y==N）&&（maze[x][y]==-1）））;??//循環(huán)
	
	if（s->top==-1）//若是入口，則無通路
		cout<<“此迷宮不通“;
	else
	{
		elem.x=x;??elem.y=y;??elem.dir=dir;//將出口坐標(biāo)入棧
		f=push（selem）;
		cout<<“迷宮通路是：“<		i=0;
		while?（i?<=?s->top）
		{
			cout<<“（“<stack[i].x<<““<stack[i].y<<“）“;//顯示迷宮通路
			if（i!=s->top）
				cout<<“-->“;
			if（（i+1）%4==0）
				cout<			i++;

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

?????文件??????14755??2009-06-09?15:14??迷宮?1071304112?匡玉龍\6891add0965945199a502775.jpg

????.......????208986??2009-06-14?12:54??迷宮?1071304112?匡玉龍\Debug\migong.exe

?????文件?????229532??2009-06-14?12:54??迷宮?1071304112?匡玉龍\Debug\migong.ilk

?????文件??????14313??2009-06-14?12:54??迷宮?1071304112?匡玉龍\Debug\migong.obj

?????文件?????263344??2009-06-14?12:54??迷宮?1071304112?匡玉龍\Debug\migong.pch

?????文件?????484352??2009-06-14?12:54??迷宮?1071304112?匡玉龍\Debug\migong.pdb

?????文件??????66560??2009-06-14?12:54??迷宮?1071304112?匡玉龍\Debug\vc60.idb

?????文件??????61440??2009-06-14?12:54??迷宮?1071304112?匡玉龍\Debug\vc60.pdb

?????文件???????4440??2009-06-08?16:42??迷宮?1071304112?匡玉龍\migong.cpp

?????文件???????3401??2009-06-14?12:54??迷宮?1071304112?匡玉龍\migong.dsp

?????文件????????520??2009-06-14?12:56??迷宮?1071304112?匡玉龍\migong.dsw

?????文件??????50176??2009-06-14?12:56??迷宮?1071304112?匡玉龍\migong.ncb

?????文件??????48640??2009-06-14?12:56??迷宮?1071304112?匡玉龍\migong.opt

?????文件????????848??2009-06-14?12:54??迷宮?1071304112?匡玉龍\migong.plg

?????文件??????57810??2009-06-14?12:56??迷宮?1071304112?匡玉龍\MyCatch.jpg

?????文件?????200192??2009-06-14?15:14??迷宮?1071304112?匡玉龍\迷宮.doc

?????文件?????114176??2009-06-10?10:43??迷宮?1071304112?匡玉龍\迷宮.ppt

?????目錄??????????0??2009-06-14?12:54??迷宮?1071304112?匡玉龍\Debug

?????目錄??????????0??2009-06-14?19:07??迷宮?1071304112?匡玉龍

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

??????????????1823485????????????????????19