迷宫.cpp

共有10个文件代码

#include <iostream.h>
#include <iomanip.h>
#define m 5 //行数
#define n 6  //列数
#define MaxSize 100
struct stype
{
	int x,y,pre;
}queue[MaxSize];
int mg[m+1][n+1]={ //四周要加上均为1的外框
	{1,1,1,1,1,1,1},
	{1,0,0,1,0,1,1},
	{1,0,1,0,1,0,1},
	{1,0,1,1,1,0,1},
	{1,1,1,0,1,0,1},
	{1,1,1,1,1,1,1}
};
int zx[8],zy[8];  //zx表示X方向的移动增量,zy表示Y方向的移动增量
void printlj(int rear)
{
	int i,j;
	i=rear;
	do
	{
		j=i;
		i=queue[i].pre;
		queue[j].pre=-1;
	}while(i!=0);
	cout<<"查找到的迷宫路径:\n\t入口->";
	i=0;
	while(i<MaxSize)
	{
		if(queue[i].pre==-1)
			cout<<"("<<queue[i].x<<","<<queue[i].y<<")->";
		i++;
	}
	cout<<"出口\n";
}
void mglj()
{
	int i,j,x,y,v,front,rear,find=0,no=1;
	queue[1].x=1;queue[1].y=1;queue[1].pre=0;//从(1，1)开始搜索，将该点插入队列
	front=1;rear=1; //队列指针置初值1
	mg[1][1]=-1;    //将其赋值-1，避免回过来重复搜索
	cout<<"步号   x  y   pre\n";
	cout<<setw(4)<<no++<<setw(4)<<queue[rear].x<<setw(4)<<queue[rear].y<<setw(4)<<queue[rear].pre<<endl;
	while(front<=rear &&!find)  //队列不为空且未找到路径时环形
	{
		x=queue[front].x;
		y=queue[front].y;
		for(v=1;v<=8;v++)  //环形遍历每个方向，把每个可走的方向插入队列中
		{
			i=x+zx[v];j=y+zy[v];  //选择一个前进方向
			if(mg[i][j]==0)      //如果该方向可走
			{
				rear++;          //将该方向插入到队列中
				queue[rear].x=i;
				queue[rear].y=j;
				queue[rear].pre=front; //指向上一个步号
				mg[i][j]=-1;     //将其赋值-1，避免回过来重复搜索
				cout<<setw(4)<<no++<<setw(4)<<queue[rear].x<<setw(4)<<queue[rear].y<<setw(4)<<queue[rear].pre<<endl;
			}
			if(i==m&&j==n)  //找到了出口
			{
				printlj(rear);  //打印找到的路径
				find=1;      //设置为1时便于退出环形
			}
		}
		front++;  //从队列中删除一个元素
	}
	if(!find)
		cout<<"无法通过"<<endl;
}
void main()
{   //zx,zy数组的方向取值
	zx[1]=-1;zx[2]=-1;zx[3]=0;zx[4]=1;  //建立方向数据
	zx[5]=1;zx[6]=1;zx[7]=0;zx[8]=-1;
	zy[1]=0;zy[2]=1;zy[3]=1;zy[4]=1;
    zy[5]=0;zy[6]=-1;zy[7]=-1;zy[8]=-1;
	cout<<"迷宫的起始坐标为(-1,-1):"<<endl;
	cout<<setw(4)<<"1  1  1  1  1  1  1"<<endl;
	cout<<setw(4)<<"1  0  0  1  0  1  1"<<endl;
	cout<<setw(4)<<"1  0  1  0  1  0  1"<<endl;
	cout<<setw(4)<<"1  0  1  1  1  0  1"<<endl;
	cout<<setw(4)<<"1  1  1  0  1  0  1"<<endl;
	cout<<setw(4)<<"1  1  1  1  1  1  1"<<endl;
	mglj();  //产生迷宫路径
}