maze.cpp

老鼠走迷宫的程序

#include "head.h"
#define MAXLENGTH 25 // 迷宫最大长度
#define MAXQSIZE 100 // 最大队列长度

typedef struct postype 
{
	int x;
	int y;
	char data;
	Status flag;//是否是围墙
	Status FLAG;//是否被标记过为围墙
	Status pass;//是否被经过
	int num;//距离起点的距离
}postype;

postype maze[MAXLENGTH][MAXLENGTH];

postype curpos;

typedef postype QElemType; 
 
struct SqQueue
 {
   QElemType *base; // 初始化的动态分配存储空间
   int front; // 头指针,若队列不空,指向队列头元素
   int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置
 };

Status InitQueue(SqQueue &Q)
 { // 构造一个空队列Q
   Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));
   if(!Q.base) // 存储分配失败
     exit(OVERFLOW);
   Q.front=Q.rear=0;
   return OK;
 }

 Status QueueEmpty(SqQueue Q)
 { // 若队列Q为空队列,则返回TRUE,否则返回FALSE
   if(Q.front==Q.rear) // 队列空的标志
     return TRUE;
   else
     return FALSE;
 }

 int QueueLength(SqQueue Q)
 { // 返回Q的元素个数,即队列的长度
   return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
 }

 Status EnQueue(SqQueue &Q,QElemType e)
 { // 插入元素e为Q的新的队尾元素
   if((Q.rear+1)%MAXQSIZE==Q.front) // 队列满
     return ERROR;
   Q.base[Q.rear].data=e.data;
   Q.base[Q.rear].flag=e.flag;
   Q.base[Q.rear].FLAG=e.FLAG;
   Q.base[Q.rear].num=e.num;
   Q.base[Q.rear].x=e.x;
   Q.base[Q.rear].y=e.y;
   Q.base[Q.rear].pass=e.pass;
   Q.rear=(Q.rear+1)%MAXQSIZE;
   return OK;
 }

 Status DeQueue(SqQueue &Q,QElemType &e)
 { // 若队列不空,则删除Q的队头元素,用e返回其值,并返回OK;否则返回ERROR
   if(Q.front==Q.rear) // 队列空
     return ERROR;
   e.data=Q.base[Q.front].data;
   e.flag=Q.base[Q.front].flag;
   e.FLAG=Q.base[Q.front].FLAG;
   e.num=Q.base[Q.front].num;
   e.x=Q.base[Q.front].x;
   e.y=Q.base[Q.front].y;
   e.pass=Q.base[Q.front].pass;
   Q.front=(Q.front+1)%MAXQSIZE;
   return OK;
 }

void print(int x,int y)
 { // 产生迷宫
   int i,j;
   for(i=0;i<x;i++)
   {
     for(j=0;j<y;j++)
     cout<<"   "<<maze[i][j].data;
     cout<<"\n";
   }
 }

Status mazepath(postype start,postype end) 
 { // 若迷宫maze中存在从入口start到出口end的通道，则求得一条
   // 存放在栈中(从栈底到栈顶)，并返回TRUE；否则返回FALSE
   int i,j;
   SqQueue q;
   QElemType e;
   InitQueue(q);
   curpos.x=start.x;
   curpos.y=start.y;
   curpos.FLAG=start.FLAG;
   curpos.flag=start.flag;
   curpos.num=start.num=0;
   curpos.pass=start.pass=TRUE;
 while(curpos.x!=end.x || curpos.y !=end.y)
  {
   
   if(maze[curpos.x][curpos.y+1].flag==FALSE && maze[curpos.x][curpos.y+1].pass==FALSE) 
   {
	   maze[curpos.x][curpos.y+1].num=curpos.num+1;
	   maze[curpos.x][curpos.y+1].pass=TRUE;
	   EnQueue(q,maze[curpos.x][curpos.y+1]);
	   
   }
   if(maze[curpos.x+1][curpos.y].flag==FALSE && maze[curpos.x+1][curpos.y].pass==FALSE )
   {	
	   maze[curpos.x+1][curpos.y].num=curpos.num+1;
	   maze[curpos.x+1][curpos.y].pass=TRUE;
	   EnQueue(q,maze[curpos.x+1][curpos.y]);
	   
   }
   if(maze[curpos.x][curpos.y-1].flag==FALSE && maze[curpos.x][curpos.y-1].pass==FALSE)
   {
	   maze[curpos.x][curpos.y-1].num=curpos.num+1;
	   maze[curpos.x][curpos.y-1].pass=TRUE;
	   EnQueue(q,maze[curpos.x][curpos.y-1]);
	   
   }
   if(maze[curpos.x-1][curpos.y].flag==FALSE && maze[curpos.x-1][curpos.y].pass==FALSE)
   {
	   maze[curpos.x-1][curpos.y].num=curpos.num+1;
	   maze[curpos.x-1][curpos.y].pass=TRUE;
	   EnQueue(q,maze[curpos.x-1][curpos.y]);
	   
   }
   DeQueue(q,e);
   curpos.x=e.x;
   curpos.y=e.y;
   curpos.flag=e.flag;
   curpos.FLAG=e.FLAG;
   curpos.num=e.num;
   curpos.pass=e.pass;
   if(QueueEmpty(q))
    return ERROR;
  }


while(curpos.num-1!=start.num)
{
   
	if(maze[curpos.x][curpos.y+1].num==curpos.num-1)
   {
		i=curpos.x,j=curpos.y+1;	
		maze[i][j].data='#';
	    curpos.x=maze[i][j].x;
		curpos.y=maze[i][j].y;
	    curpos.flag=maze[i][j].flag;
        curpos.FLAG=maze[i][j].FLAG;
		curpos.num=curpos.num-1;
   }
else if(maze[curpos.x+1][curpos.y].num==curpos.num-1)
   {
	    i=curpos.x+1,j=curpos.y;	
	    maze[i][j].data='#';
	    curpos.x=maze[i][j].x;
		curpos.y=maze[i][j].y;
	    curpos.flag=maze[i][j].flag;
        curpos.FLAG=maze[i][j].FLAG;
		curpos.num=curpos.num-1;
   }
else if(maze[curpos.x][curpos.y-1].num==curpos.num-1)
   {
	    i=curpos.x,j=curpos.y-1;	
	    maze[i][j].data='@';
	    curpos.x=maze[i][j].x;
		curpos.y=maze[i][j].y;
	    curpos.flag=maze[i][j].flag;
        curpos.FLAG=maze[i][j].FLAG;
		curpos.num=curpos.num-1;
   }
else if(maze[curpos.x-1][curpos.y].num==curpos.num-1)
   {
        i=curpos.x-1,j=curpos.y;	
	    maze[i][j].data='@';
	    curpos.x=maze[i][j].x;
		curpos.y=maze[i][j].y;
	    curpos.flag=maze[i][j].flag;
        curpos.FLAG=maze[i][j].FLAG;
		curpos.num=curpos.num-1;
   } 
}
  return OK;
}

void main()
{  
   system("color 0c");
   postype begin,end;
   int i,j,x,y,x1,y1,count=0;
   cout<<"请输入迷宫的行列数(外墙)：";
   cin>>x>>y;
   for(i=0;i<x;i++) // 定义周边值为*(同墙)
   {
     maze[0][i].data='%'; // 行周边
     maze[x-1][i].data='%';
   }
   for(j=1;j<y-1;j++)
   {
     maze[j][0].data='%'; // 列周边
     maze[j][y-1].data='%';
   }
   for(i=1;i<x-1;i++)
     for(j=1;j<y-1;j++)
	 { 
		 maze[i][j].flag=FALSE;
		 maze[i][j].x=i;
		 maze[i][j].y=j;
		 maze[i][j].num=1000;
		 maze[i][j].data=0; // 定义通道初值为0
		 maze[i][j].FLAG=FALSE;//标志位为FALSE
		 maze[i][j].pass=FALSE;
	 }
   cout<<"请输入迷宫的障碍数：";
   cin>>j;
   srand((unsigned)time(NULL)); 
	while(count<j)
	{
		x1=rand()%x;
		y1=rand()%y;
		if(x1>0&&y1>0)
		{
			if(x1<x-1&&y1<y-1)
			{
				if(maze[x1][y1].FLAG!=TRUE)
					{
						maze[x1][y1].data='%';
						maze[x1][y1].FLAG=TRUE;
						maze[x1][y1].num=1000;
						maze[x1][y1].flag=TRUE;
						count++;
					}
			}
		}
	}
   cout<<"迷宫如下:\n";
   print(x,y);
   cout<<"请输入起点的行列数：\n";
   cin>>begin.x>>begin.y;
   cout<<"请输入终点的行列数：\n";
   cin>>end.x>>end.y;
   maze[begin.x][begin.y].data='A';
   maze[end.x][end.y].data='Z';
   if(mazepath(begin,end)) // 求得一条通路
   {
	 cout<<"此迷宫从入口到出口的一条路径如下:\n";
	 system("color 0e");
     print(x,y); // 输出此通路
   }
   else
     cout<<"此迷宫没有从入口到出口的路径\n";
 }