migong.cpp

迷宫的实现

//从队列中取出步骤数据，放入栈中
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define M 10 // 迷宫行数(包括外墙)
#define N 10 // 迷宫列数(包括外墙)
#define ET 8
#define FR 4
#define STACKSIZE 10
#define STACKINSERT 2
#define QSIZE 10
#define D 4
FILE *fp1=fopen("c:\\d1.txt","r");
FILE *fp=fopen("c:\\d2.txt","w");
typedef struct 
{
	int x,y;//点在迷宫中的坐标
	int fro;//在队列的时候用来标记能直达该点的前一个点在队列中的位置
	char ch;//点的标记,1表示通道，0表示墙壁
}QElemType,SElemType;//迷宫点的类型
struct SqStack
{
	SElemType *base;
	SElemType *top;
	int sqstacksize;
};//栈
struct SqQueue
{
	QElemType *base;
	int front;
	int rear;
};//队列
struct 
{
	int x,y;
}move[4]={{0,1},{1,0},{0,-1},{-1,0}};//向四个方向移动的量，优先级为：下，右，上，左
int creatSqStack(SqStack &S)//建立栈
{
	S.base = (SElemType *)malloc(STACKSIZE*sizeof(SElemType));
	if(!S.base)
		exit(0);
	S.top=S.base;
	S.sqstacksize = STACKSIZE;
	return 1;
}
int creatSqQueue(SqQueue &Q)//建立队列
{
	Q.base = (QElemType *)malloc(QSIZE*sizeof(QElemType));
	if(!Q.base)
		exit(0);
	Q.front=Q.rear=0;
	return 1;
}
int EnterQueue(SqQueue &Q,QElemType &e)//入队列
{
	if(Q.rear>=QSIZE)
	{
		Q.base= (QElemType *)realloc(Q.base,(Q.rear+1)*sizeof(QElemType));
		if(!Q.base)
			return 0;
	}
	*(Q.base+Q.rear)=e;//////////////////
	Q.rear++;
	return 1;
}
int QueueEmpty(SqQueue Q)//检测队列是否为空
{
	if(Q.front==Q.rear)
		return 1;
	else
		return 0;
}
int DeQueue(SqQueue &Q,QElemType &e)//删除队列的一个点
{
	if(Q.front==Q.rear) // 队列空
		return 0;
	e=*(Q.base+Q.front);
	Q.front=Q.front+1;
	return 1;
}
int EnterStack(SqStack &S,SElemType &e)//进栈
{
	if(S.top-S.base==S.sqstacksize)
	{
		S.base=(SElemType*)realloc(S.base,(S.sqstacksize+STACKINSERT)*sizeof(SElemType));
		if(!S.base)
			exit(0);
		S.top=S.base+S.sqstacksize;
		S.sqstacksize +=STACKINSERT;
	}
	*(S.top)++=e;
	return 1;
}
int StackEmpty(SqStack S)//栈是否为空
{
	if(S.top==S.base)
		return 1;
	else
		return 0;
}
int Pop(SqStack &S,SElemType &e)//从栈总弹出一个点
{
	if(S.top==S.base)
		return 0;
	else
		e=*--S.top;
	return 1;
}
int findway(int m[M][N])
{
	SqStack S;//栈
	SqQueue Q;//队列
	QElemType now,next;//迷宫的点
	int ex,ey;
	int i,k;
	int over=1;//查找变量，如果找到，将其直改为0，否则不变
	
	/////////////////////////从文件中读入迷宫的入口和出口///////////////////////////////
	printf("<从文件输入起始点的位置（从<1，1>开始).......>\n");
	fscanf(fp1,"%d %d",&now.x,&now.y);//当前文件指针定位在迷宫后的位置
	
	printf("<从文件输入出迷宫的点的位置(最右端为:<%d,%d>).......>\n",M-2,N-2);
	fscanf(fp1,"%d %d",&ex,&ey);
	printf("<输入成功>\n");
	/////////////////////////////////////////////////////////////////////////////////////
	
	now.fro=-1;
	m[now.x][now.y]=-1;//通过更改值来标记走过过的点
	creatSqQueue(Q);//建立一个队列
	EnterQueue(Q,now);//将当前的点进入队列
	while(!QueueEmpty(Q)&&over)//队列不为空并且没有找到出口
	{
		DeQueue(Q,now);//获得当前队列顶点，方便查找下一个点
		if(now.x == ex && now.y == ey)
			over=0;
		else
		{
			///////////////////将当前点能通达的点都进入队列///////////////////////////////////////
			for(i=0;i<D;i++)//宏定义D为4，表示为四维迷宫
			{
				next.x=now.x+move[i].x;
				next.y=now.y+move[i].y;//继续探索
				if(m[next.x][next.y]==1)//能走
				{
					m[next.x][next.y]=-1;//标记该点已经被探索
					next.fro=Q.front-1;//存储上个步骤地地址,即在队列中的位置队列中的形态为一个点后面紧跟它能通达的点
					//所以需要标记下每个点的上一个点的队列中的位置
					EnterQueue(Q,next);//当前的点进队列
					if(next.x==ex&&next.y==ey)//找到了出口
					{
						over=0;//更改over的值表示已经找到出口
						break;
					}
				}
			}	
			////////////////////////////////////////////////////////////////////////////////////
		}
	}
	
	if(over)//找不到出口
	{ 
		printf("<找不到路径>\n");
		fprintf(fp,"<找不到路径>\n");
		return 0;
	}
	else  
	{
		creatSqStack(S); //准备一个空栈
		i=Q.rear-1; // i为待入栈元素在队列中的位置，以为当前的条件为找到了出口，所以即为出口的点在队列中的位置，即队尾
		
		//将队列中的元素放到栈中，从队尾开始，放入栈中，从栈中出来的顺序即为路径的正常路径/////////////
		while(i>=0) // 没到入口
		{
			EnterStack(S,*(Q.base+i));
			i=(*(Q.base+i)).fro; // i为前一元素在队列中的位置
		}
		////////////////////////////////////////////////////////////////////////////////////////////////
		i=0; // i为走出迷宫的步骤
		printf("\n\n走出迷宫的一个方案：\n");
		fprintf(fp,"\n走出迷宫的一个方案：\n");
		/////////////////////////////路径打印///////////////////////////////////////////
		while(!StackEmpty(S))
		{
			Pop(S,now);
			i++;
			m[now.x][now.y]=9;//将能走的点改为9，方便打印出来
			printf("(%d,%d)",now.x,now.y);//打印到屏幕
			if(i%8==0)
				printf("\n");
			fprintf(fp,"(%d,%d)",now.x,now.y);
			fprintf(fp,"\n");
		}
		///////////////////////////////////////////////////////////////////////////////////
		printf("\n\n示意图为:\n");
		//使解直观，显示处理后的迷宫
		for(i=1;i<M-1;i++) // 输出
		{
			for(k=1;k<N-1;k++)
			{
				if(m[i][k]==9)
					printf("%5c",'#');//能走的点该为#
				else
					printf("%5d",m[i][k]);//不能走的点输出数字
			}
			printf("\n");			
		}
		printf("注：#表示当前路径，-1表示曾经探索但失败的点\n");
		return 1;
	} 
}
int main()
{
	int i,k;
	int migong[M][N];
	printf("迷宫包括%d行，%d列\n",M-2,N-2);//宏定义而来，定义迷宫的长度和宽度
	////////////////////////给迷宫加上外墙，防止探索时候出界//////////////////////////////
	for(i=0;i<M-1;i++)
	{
		migong[i][0]=0;
		migong[i][N-1]=0;
	}//左右外墙
	for(k=0;k<=N-1;k++)
	{
		migong[0][k]=0;
		migong[M-1][k]=0;
	}//上下外墙
	///////////////////////////////////////////////////////////////////////////////////////
	printf("从文件d1.txt输入迷宫（0为墙，1为通路，不包括附加边界）：\n");
	///////////////////////////////从文件读入迷宫//////////////////////////////////////////
	for(i=1;i<M-1;i++)
		for(k=1;k<N-1;k++)
			fscanf(fp1,"%d",&migong[i][k]);
		///////////////////////////////////////////////////////////////////////////////////////
		printf("\n");
		/////////////////////////////打印加了外墙后的迷宫/////////////////////////////////////
		for(i=0;i<M;i++)
		{
			for(k=0;k<N;k++)
				printf("%5d",migong[i][k]);
			printf("\n");
		}
		printf("\n");
		/////////////////////////////////////////////////////////////////////////////////////////
		
		/////////////////////////找迷宫路径////////////////////////////////////////////////////
		findway(migong);//调用函数
		////////////////////////////////////////////////////////////////////////////////////////
		
		//////////////////////////关闭文件///////////////////////////////////////////////////////
		fclose(fp);
		fclose(fp1);
		////////////////////////////////////////////////////////////////////////////////////////
		return 1;
}