迷宫问题数据结构 C++编写

迷宫；入口；穷举求解；方向；出口 从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。设计一个计算机程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

#define M2 12 /*M2*N2为实际使用迷宫数组的大小*/
#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
	 //定义方向位移数组的元素类型对于存储坐标增量的方向位移数组move
 { int dxdy;};

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

 void inimaze（int maze[][N2]）////初始化迷宫
 {
	 int ijnum;
	 for（i=0j=0;i<=M+1;i++）//设置迷宫边界
		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;//根据MN的值产生迷宫
			 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[]）//初始化方向位移数组
{//依次为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;/*栈不满，执行入栈操作*/
		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;   //设[1][1]为入口处
	do 
	{
		x=i+move[dir].dx;//球下一步可行的到达点的坐标
		y=j+move[dir].dy;
		if（maze[x][y]==0）
		{
			elem.x=i;elem.y=j;elem.dir=dir;
			f=push（selem）;//如果可行将数据入栈
			if（f==false）//如果返回假，说明栈容量不足
				cout<<“栈长不足“;
			i=x;j=y;dir=0;maze[x][y]=-1;
		}
		else
			if （dir < 7）
				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）））;  //循环
	
	if（s->top==-1）//若是入口，则无通路
		cout<<“此迷宫不通“;
	else
	{
		elem.x=x;  elem.y=y;  elem.dir=dir;//将出口坐标入栈
		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