迷宫算法.cpp

数据结构迷宫算法 数据结构迷宫算法

#include <iostream.h>
#include <stdlib.h>
#define MAXSIZE 1024
#define M 1024
#define N 1024
int maze[M][N];//定义迷宫数组
typedef struct
{
	int x;
	int y;
}item;
item move[8];//定义方向变量数组
typedef struct
{
	int x,y,d;		//横纵坐标及方向
}datatype;
typedef struct
{
	datatype data[MAXSIZE];
	int top;
}Seqstack;
Seqstack *Init_Seqstack()//栈初始化
{
	Seqstack *s;
	s=new Seqstack;
	if(!s)
	{
		cout<<"空间不足!\n";
		return NULL;
	}
	else
	{
		s->top=-1;
		return s;
	}
}
int Empty_Seqstack(Seqstack *s)//判断栈空
{
	if(s->top==-1)
		return 1;
	else
		return 0;
}
int Push_Seqstack(Seqstack *s,datatype x)//入栈
{
	if(s->top==MAXSIZE-1)
		return 0;
	else
	{
		s->top++;
		s->data[s->top]=x;
		return 1;
	}
}
int Pop_Seqstack(Seqstack *s,datatype *x)//出栈
{
	if(Empty_Seqstack(s))
		return 0;
	else
	{
		*x=s->data[s->top];
		s->top--;
		return 1;
	}
}
void creat(int maze[M][N],int m,int n)//创建迷宫
{
	int a,i,j;
	for(i=0;i<m+2;i++)//定义迷宫边界
	{
		maze[0][i]=1;
		maze[m+1][i]=1;
	}
	for(j=0;j<n+2;j++)//定义迷宫边界
	{
		maze[j][0]=1;
		maze[j][n+1]=1;
	}
	for(i=1;i<m+1;i++)//输入迷宫数据
	{
		for(j=1;j<n+1;j++)
		{
			cout<<"请输入第"<<i<<"行第"<<j<<"个数据:";
			cin>>a;
			maze[i][j]=a;
		}
	}
	cout<<"所建迷宫为: \n";
	for(i=1;i<m+1;i++)//输出所建迷宫
	{
		for(j=1;j<n+1;j++)
			cout<<maze[i][j]<<'\0';
		cout<<endl;
	}
}
void Init_move()//定义方向变量
{
	move[0].x=0;
	move[0].y=1;
	move[1].x=1;
	move[1].y=1;
	move[2].x=1;
	move[2].y=0;
	move[3].x=1;
	move[3].y=-1;
	move[4].x=0;
	move[4].y=-1;
	move[5].x=-1;
	move[5].y=-1;
	move[6].x=-1;
	move[6].y=0;
	move[7].x=-1;
	move[7].y=1;
}
int path(int m,int n,Seqstack *s,int a1,int a2,int b1,int b2)//寻找迷宫出口
{
	datatype temp;
	int x,y,d,i,j;
	temp.x=a1;
	temp.y=a2;//定义入口
	temp.d=-1;
	Push_Seqstack(s,temp);
	while(!Empty_Seqstack(s))
	{
		Pop_Seqstack(s,&temp);
		x=temp.x;
		y=temp.y;
		d=temp.d+1;
		while(d<8)
		{
			i=x+move[d].x;
			j=y+move[d].y;
			if(maze[i][j]==0)
			{
				temp.x=x;
				temp.y=y;
				temp.d=d;
				Push_Seqstack(s,temp);
				x=i;
				y=j;
				maze[x][y]=-1;
				if(x==b1&&y==b2)//判断是否达到出口
					return 1;
				else
					d=0;
			}
			else
				d++;
		}
	}
	return 0;
}
void show(Seqstack *s,int b1,int b2)//输出迷宫路径
{
	int i=0;
	for(;i<s->top+1;i++)
		cout<<"("<<s->data[i].x<<","<<s->data[i].y<<")"<<"-->";
	cout<<"("<<b1<<","<<b2<<")"<<endl;
}
void main()
{
	Seqstack *s;
	int m,n,p,a1,a2,b1,b2;
	cout<<"请输入迷宫的实际行、列：\n";
	cin>>m>>n;
	creat(maze,m,n);
	s=Init_Seqstack();
	Init_move();
	cout<<"请输入迷宫的入口及出口(坐标格式): \n";
	cin>>a1>>a2>>b1>>b2;
	p=path(m,n,s,a1,a2,b1,b2);
	
	if(p==1)
	{
		cout<<"迷宫有路,路径为: \n";
		show(s,b1,b2);
	}
	else
		if(p==0)
			cout<<"迷宫无路\n";
		else
			cout<<"操作失败!\n";
}