迷宫问题.cpp

这是我个人做的在vc环境下的迷宫问题的实现。各位可以参考或指教！

//base.h
#include <stdio.h>
#include< iostream.h>
#include <stdlib.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
 
//stack.h
//#include "base.h"
#define INIT_SIZE 100 //存储空间初始分配量
#define INCREMENT 10  //存储空间分配增量
typedef struct{       //迷宫中r行c列的位置
	int r;
	int c;
}PostType;
typedef struct{
	int ord;      //当前位置在路径上的序号
	PostType seat;//当前坐标
	int di;       //往下一坐标的方向
}SElemType;        //栈元素类型
typedef struct{
	SElemType* base;//栈基址,构造前销毁后为空
	SElemType* top;//栈顶
	int stackSize;  //栈容量
}Stack;             //栈类型
Status InitStack(Stack &S){	//构造空栈s
	S.base=(SElemType*)malloc(INIT_SIZE *sizeof(SElemType));
	if(!S.base)
		exit(OVERFLOW);//存储分配失败
	S.top=S.base;
	S.stackSize=INIT_SIZE;
	return OK;
}//InitStack
Status StackEmpty(Stack S){	
//若s为空返回TRUE,否则返回FALSE
	if(S.top==S.base)
		return TRUE;
	return FALSE;
}//StackEmpty
Status Push(Stack &S,SElemType e){
 //插入元素e为新的栈顶元素
	if(S.top-S.base >=S.stackSize){//栈满，加空间
		S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType));
		if(!S.base)
			exit(OVERFLOW);   //存储分配失败
		S.top=S.base+S.stackSize;
		S.stackSize+=INCREMENT;
	}
	*S.top++=e;
	return OK;
}//push
Status Pop(Stack &S,SElemType &e){//若栈不空删除栈//顶元素用e返回并返回OK，否则返回ERROR
	if(S.top==S.base)
		return ERROR;
	e=*--S.top;
	return OK;
}//Pop
Status DestroyStack(Stack &S){//销毁栈S,
	free(S.base);
	S.top=S.base;
	return OK;
}//DestroyStack
 
//maze.cpp
//#include "stack.h"
#define MAXLEN 10//迷宫包括外墙最大行列数目
typedef struct{
	int r;
	int c;
	char adr[MAXLEN][MAXLEN];//可取' ''*' '@' '#'
}MazeType;   //迷宫类型
Status InitMaze(MazeType &maze){
//初始化迷宫若成功返回TRUE,否则返回FALSE
	int m,n,i,j;
	cout<< "Enter row and column numbers: ";
	cin>>maze.r>>maze.c; //迷宫行和列数
	for(i=0;i<=maze.c+1;i++){//迷宫行外墙
		maze.adr[0][i]='#';
		maze.adr[maze.r+1][i]='#';
	}//for
	for(i=0;i<=maze.r+1;i++){//迷宫列外墙
		maze.adr[i][0]='#';
		maze.adr[i][maze.c+1]='#';
	}
	for(i=1;i<=maze.r;i++)
		for(j=1;j<=maze.c;j++)
			maze.adr[i][j]=' ';//初始化迷宫
	cout<<"Enter block's coordinate((-1,-1) to end): ";
	cin>>m>>n;//接收障碍的坐标
	while(m!=-1){
		if(m>maze.r || n>maze.c)//越界
			exit(ERROR);
		maze.adr[m][n]='#';//迷宫障碍用'#'标记
		cout<<"Enter block's coordinate((-1,-1) to end): ";
		cin>>m>>n;
	}//while
	return OK;
}//InitMaze	
Status Pass(MazeType maze,PostType curpos){
//当前位置可通则返回TURE,否则返回FALSE
	if(maze.adr[curpos.r][curpos.c]==' ')//可通
		return TRUE;
	else
		return FALSE;
}//Pass
Status FootPrint(MazeType &maze,PostType curpos){
//若走过并且可通返回TRUE,否则返回FALSE
//在返回之前销毁栈S
	maze.adr[curpos.r][curpos.c]='*';//"*"表示可通
	return OK;
}//FootPrint
PostType NextPos(PostType &curpos,int i){
//指示并返回下一位置的坐标
	PostType cpos;
	cpos=curpos;
	switch(i){        //1.2.3.4分别表示东,南,西,北方向
		case 1 : cpos.c+=1; break;
		case 2 : cpos.r+=1; break;
		case 3 : cpos.c-=1; break;
		case 4 : cpos.r-=1; break;
		default: exit(ERROR);	
	}
	return cpos;
}//Nextpos
Status MarkPrint(MazeType &maze,PostType curpos){
//曾走过但不是通路标记并返回OK
	maze.adr[curpos.r][curpos.c]='@';//"@"表示曾走过但不通
	return OK;
}//MarkPrint
Status MazePath(MazeType &maze,PostType start,PostType end){
	//若迷宫maze存在从入口start到end的通道则求得一条存放在栈中
	//并返回TRUE,否则返回FALSE
	Stack S;
	PostType curpos;
	int curstep;//当前序号,1.2.3.4分别表示东,南,西,北方向
	SElemType e;
	InitStack(S);
	curpos=start; //设置"当前位置"为"入口位置"
	curstep=1;   //探索第一步
	do{
		if(Pass(maze,curpos)){//当前位置可以通过,
//即是未曾走到过的通道
			FootPrint(maze,curpos);//留下足迹
			e.ord=curstep;
			e.seat=curpos;
			e.di=1;
			Push(S,e);              //加入路径
			if(curpos.r==end.r&& curpos.c==end.c)
if(!DestroyStack(S))//销毁失败
exit(OVERFLOW);
else 
	 return TRUE; //到达出口
			else{
				curpos=NextPos(curpos,1); 
//下一位置是当前位置的东邻
				curstep++;       //探索下一步
			}//else
		}//if
		else{    //当前位置不通
			if(!StackEmpty(S)){
				Pop(S,e);
				    while(e.di==4
&& !StackEmpty(S)){
					MarkPrint(maze,e.seat);
					Pop(S,e);        
//留下不能通过的标记,并退一步
				}//while
				if(e.di < 4){
					e.di++;//换下一个方向探索
					Push(S,e);            
					curpos=NextPos(e.seat,e.di);//设定当前位置是该
//新方向上的相邻
				}//if
			}//if
		}//else
	}while(!StackEmpty(S));
	if(!DestroyStack(S))//销毁失败
	   exit(OVERFLOW);	    
 else 
	   return FALSE;
}//MazePath
void PrintMaze(MazeType &maze){
//将标记路径信息的迷宫输出到终端(包括外墙)
	int i,j;
	cout<<"\nShow maze path(*---pathway):\n\n";
	cout<<"  ";
	for(i=0;i<=maze.r+1;i++)//打印列数名
		cout<<" "<<i;
	cout<<"\n"<<"\n";
	for(i=0;i<=maze.r+1;i++){
		cout<<" "<<i;//打印行名 
		for(j=0;j<=maze.c+1;j++)
	cout<<" "<<maze.adr[i][j];//输出迷宫//当前位置的标记          
		cout<<"\n"<<"\n";
	}
}//PrintMaze
 
void main(){     //主函数
	MazeType maze;
	PostType start,end;
	char cmd;
	do{
		cout<<"-------FOUND A MAZEPATH--------\n";
		if(!InitMaze(maze)){  //初始化并创建迷宫
		cout<<"\nInitialization errors!!!\n";
			exit(OVERFLOW);     //初始化错误
		}
		do{                 //输入迷宫入口坐标
			cout<<"\nEnter entrance coordinate of the maze: ";
			cin>>start.r>>start.c;
			if(start.r>maze.r || start.c>maze.c){
				cout<<"\nBeyond the maze!!!\n";
				continue;
			}
		}while(start.r>maze.r || start.c>maze.c);
		do{                 //输入迷宫出口坐标
			cout<<"\nEnter exit coordinate of the maze: ";
			cin>>end.r>>end.c;
			if(end.r>maze.r || end.c>maze.c){
				cout<<"\nBeyond the maze!!!\n";
				continue;
			}
		}while(end.r>maze.r || end.c>maze.c);
		if(!MazePath(maze,start,end))//迷宫求解
			cout<<"\nNo path from entrance to exit!\n";
		else
			PrintMaze(maze);//打印路径
	cout<<"\nContinue?(y/n): ";
		cin>>cmd;
	}while(cmd=='y' || cmd=='Y');
}//main