(jing)migong.cpp

数据结构课程设计 迷宫 自行画图

#include<iostream.h>
#include <stdlib.h>
#include<iomanip.h>
#define STACK_INIT_SIZE   100    //初始栈大小
#define STACKINCREAMENT   10    //添加栈的长度
#define SIZE_OF_MAPH      20     //迷宫高度
#define SIZE_OF_MAPW      20    //迷宫长度

typedef struct
{   //用来描述迷宫单元的信息,pass=1表示通行,0表示不同,
	//footprint=0,表示未走过,1表示已经过;
int  pass;
int footprint;
}MazeCell;

typedef struct
{
	int x;
	int y;
}PosType;

typedef struct
{
	int ord;
	PosType seat;
	int di;
}SElemType;

typedef struct
{           //定义栈
	SElemType *base;
	SElemType *top;
	int stacksize;
}SqStack;


int InitStack(SqStack &S)               //建立一个空栈
{
	S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
	if(!S.base) 
		exit(0);
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return 1;
}

int Push(SqStack &S,SElemType e)       //插入元素e为栈顶元素
{
	if(S.top-S.base>=S.stacksize)
	{
		S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREAMENT)*sizeof(SElemType));
		if(!S.base)
			exit(0);
		S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCREAMENT;
	}
	*S.top++=e;
	return 1;
}
int Pop(SqStack &S,SElemType &a)      //删除栈顶元素,并用a返回其值
{
	if(S.top==S.base)
		return 0;
	S.top--;
    a=*S.top;
	return 1;
}

int CheckStack(SqStack &S,int x,int y)    //判断栈内是否存在元素e,使得e.seat.x=x&&e.seat.y=y,若有则返回e.di,否则返回0
{
	SElemType *p;
	p=S.base;
	while(p!=S.top)
	{
		if(((*p).seat.x==x)&&((*p).seat.y==y))
		{
			return((*p).di);
		}
		p++;
	}
	return 0;
}

void DisplayWay(SqStack &S,int ma[SIZE_OF_MAPH][SIZE_OF_MAPW],int w,int h)    //显示走出迷宫的路径
{
	cout<<"迷宫路径如下图): "<<endl; int i,j;
    for(i=0;i<h+2;i++)
	{ 
   for(j=0;j<w+2;j++)

   {
	   
	   if (ma[i][j]==0)
		   cout<<"█";
	   else 
	   {
		   int m;
		   m=CheckStack(S,i,j);
		   switch(m)
		   {
		   case 1:cout<<"→";break;
		   case 2:cout<<"↓";break;
		   case 3:cout<<"←";break;
		   case 4:cout<<"↑";break;
		   default:cout<<"  ";
		   }
	   }
   }
   cout<<endl;
  }
cout<<endl;
	
}


int PutIn(int ma[SIZE_OF_MAPH][SIZE_OF_MAPW],int w,int h) //输入迷宫矩阵
{
	cout<<"请输入迷宫,1代表可通,0代表不通:"<<endl;
	for(int i=1;i<=w;i++)
	{	for(int j=1;j<=h;j++)
			cin>>ma[i][j];
	}
	//迷宫的外面加上一圈墙壁
	for(int j=0;j<=h+1;j++)
	{
		ma[0][j]=0;
		ma[w+1][j]=0;
	}
	for(int t=1;t<=w;t++)
	{
		ma[t][0]=0;
		ma[t][h+1]=0;
	}
	return 1;
}
	


               // 建立迷宫数组;将整数数组值赋给迷宫;
void BuideMaze(MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW],int ma[SIZE_OF_MAPH][SIZE_OF_MAPW])
{
  for(int i=0;i<SIZE_OF_MAPH;i++)
  {
   for(int j=0;j<SIZE_OF_MAPW;j++)
   {
    Map[i][j].pass=ma[i][j]; 
    Map[i][j].footprint=0;
   }
  }
}

int Pass(PosType curpos,MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW])  //判断当前块是否可通,1可通,0不可通
{
	int p=0;
if(Map[curpos.x][curpos.y].pass==1)
{
  p+=1;
}
 if(Map[curpos.x][curpos.y].footprint==0)
{
  p+=1;
}
if(p==2)
return 1;
else
return 0;
}

void Footprint(PosType curpos,MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW]) //标记已经过的块
{
	Map[curpos.x][curpos.y].footprint=1;
}

PosType Nextpos(PosType curpos,int di)   //切换下一位置为当前位置
{
	if(di==1)
	    curpos.y +=1;
	else if(di==2)
		curpos.x +=1;
	else if(di==3)
		curpos.y -=1;
	else if(di==4)
		curpos.x -=1;
	return curpos;
}

void DisplayMaze(int ma[SIZE_OF_MAPH][SIZE_OF_MAPW],int w,int h)   //显示迷宫地图
{
	system("cls");
cout<<"迷宫地图为(1代表可以通过；0代表不可以通过): "<<endl;
    for(int i=0;i<h+2;i++)
	{ 
   for(int j=0;j<w+2;j++)

   {
	   
	   if (ma[i][j]==0)
		   cout<<"█";
	   else if(ma[i][j]==1)
		   cout<<"  ";
   }
   cout<<endl;
  }
cout<<endl;
}

//void DisplayWay(
//关键函数
int MazePath(MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW],PosType start,PosType end,SqStack &S)
{
	
	InitStack(S);
	PosType curpos;   curpos=start;
	int curstep=1;
	do{
		if(Pass(curpos,Map))
		{
			Footprint(curpos,Map);
			SElemType e;
			e.ord=curstep;e.seat=curpos;e.di=1;
			Push(S,e);	
			if(curpos.x==end.x&&curpos.y==end.y) 
			{
				return(true);
			}
			
			curpos=Nextpos(curpos,1);     //切换下一位置为当前位置
		    curstep++;                    //探索下一步
			
		}//if
		else
		{
		
			if(S.base!=S.top)
			{
				SElemType a;
				Pop(S,a);
				while(a.di==4&&(S.base!=S.top))
				{
					Pop(S,a);
				}
				if(a.di<4)
				{
					a.di+=1;
					Push(S,a);
					curpos=Nextpos(a.seat,a.di);
				}
			}
		}//else
	}while(S.base!=S.top);
	return(false);
}

void main()
{
	SqStack S;
	MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW];
	int w,h;
	cout<<"请输入迷宫的行数和列数:"<<endl;
	cin>>w>>h;cout<<endl;
	int migong[SIZE_OF_MAPH][SIZE_OF_MAPW];
	//输入迷宫;
	PutIn(migong,w,h);
	//显示迷宫地图;
	DisplayMaze(migong,w,h);
	//创建迷宫数组;
	BuideMaze(Map,migong);
	PosType start,end;
	cout<<"请输入入口坐标(x,y):";cin>>start.x>>start.y;
	cout<<endl<<"请输入出口坐标(x,y):";cin>>end.x>>end.y;
	cout<<endl;
	//求解迷宫路径;
    MazePath(Map,start,end,S);
	//显示迷宫出路;
	DisplayWay(S,migong,w,h);
	
}