迷宫（队列）.cpp

用数据结构中的队列实现解决迷宫问题的程序

/*实验题目：迷宫路径(队列)
  开发思想：在这个算法中寻找一个迷宫路径，其实和用栈是差不多的，只
			是把存储的方法改为用队列存储而已。因此同样，要想着靠着
			墙壁走就行了。这里我也是用走四个方向的方法来找出一条可
			通的路径。不同的是我用队列来保存每次走过的路，运用递归
			调用以及回朔来每一次的搜索和判断。其实如果要用八个方向
			来走的话，只要在Serch函数中添加四个方向就可以了。
  开发人员：葛兴高
  开发日期：2004、10、20
  开发版本：1.0
*/
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>


typedef struct		//坐标结点
{
	int x;
	int y;
}Point;

struct  LinkNode	//链式队列结点
{
	Point data;
	LinkNode *next;
};

class MiGong
{	
public:
	MiGong();
	int Serch(int x,int y,int n,int l);		//用于寻找点(x,y)四个方向是否可行
	void RandMap(int x,int y);				//x表示X轴，y表示Y轴
	void BiginGo(int x,int y,int n,int l);	//(x,y)表示入口
	void EnQueue(int x,int y);				//把点(x,y)入列
	int	 DelQueue();						//把没有通路的点出列
	int  IsEmpty();							//判断队列是否空
	int Temp[100][100];						//迷宫的二维矩阵

private:
	LinkNode *front;
	LinkNode *rear;

};

int m=0;
//----------------------------------------------------------
//构造函数初始化
MiGong::MiGong()
{
	LinkNode *p;
	p=new LinkNode;
	front=rear=p;
}
//----------------------------------------------------------
//入列操作
void MiGong::EnQueue(int x,int y)
{
	LinkNode *p;
	p=new LinkNode;
	
	p->data.x = x;
	p->data.y = y;
	rear->next =p;
	rear = p;
}
//----------------------------------------------------------
//出列操作
int MiGong::DelQueue ()
{
	LinkNode *p;
	p=new LinkNode;

	if(!IsEmpty())
	{
		p=front;
		front=front->next;
		delete p;
		return 1;
	}

}
//----------------------------------------------------------
//判断链队列是否为空
int MiGong::IsEmpty ()
{
	if (front==rear)
		return 0;
	else
		return 1;
}
//----------------------------------------------------------
void MiGong::RandMap (int x,int y)
{
	//srand( (unsigned)time( NULL ) );
	int i,j;	//i表示X轴，j表示Y轴
	for (j=0;j<y+2;j++)
		for (i=0;i<x+2;i++)
			Temp[i][j]=1;
	for (j=1;j<y+1;j++)
		for (i=1;i<x+1;i++)
			Temp[i][j]=0;
	for (j=1;j<y+1;j++)
		for (i=1;i<x+1;i++)
		{
			if(i%2==0 && j%3==0)		//使随机产生的地图有通路的机会增加
				continue;
			Temp[i][j]=rand()%2;	//随机产生一个迷宫地图
		}
}
//----------------------------------------------------------
void MiGong::BiginGo (int x,int y,int n,int l)
{
	Temp[0][n]=Temp[x+1][l]=0;
	Serch(0,n,x+1,l);
}
//----------------------------------------------------------
int MiGong::Serch (int x,int y,int n,int l)	//n,l用来判断是否到了出口
{
	int i;
	EnQueue(x,y);	//记录每一个走过的结点
	if (x==n && y==l && m!=1)
	{
		Temp[x][y]=-1;
		m=1;
		return 1;
	}
	else 
	if (Temp[x][y]==0&&m==0)
	{
		for (i=1;i<6;i++)
		{
			Temp[x][y]=-1;
			if (i==1&&m==0) Serch(x+1,y,n,l);	//向右
			if (i==2&&m==0) Serch(x,y+1,n,l);	//向下
			if (i==3&&m==0) Serch(x-1,y,n,l);	//向左
			if (i==4&&m==0) Serch(x,y-1,n,l);	//向上
			if (i==5&&m==0) {DelQueue();Temp[x][y]=0;}
		}
	}
	else
		if(!IsEmpty())
			DelQueue();
}

void main()
{
	int i,j;
	int a,c;
	MiGong M;

	cout<<"请输入X轴的大小:";
	cin>>a;
	cout<<"请输入Y轴的大小:";
	cin>>c;

	M.RandMap (a,c);

	for (j=0;j<c+2;j++)
	{
		for (i=0;i<a+2;i++)
			printf("%3d",M.Temp[i][j]);
		cout<<endl;
	}
	int b,d;
	cout<<"输入入口位置:";
	cin>>b;
	cout<<"输入出口位置:";
	cin>>d;
	M.BiginGo (a,c,b,d);
	
	for (j=0;j<c+2;j++)
	{
		for (i=0;i<a+2;i++)
			printf("%3d",M.Temp[i][j]);
		cout<<endl;
	}
	getch();
}