maze.txt

学生作业迷宫程序（含注释

#define FALSE 0;
#define TRUE 1;
#define NULL 0;
#include<iostream.h>
#include<stdio.h>
typedef struct maze{
	char location[100][100];    //存储迷宫的二维数组
	int row;                    //迷宫行数
	int col;                    //迷宫列数
}maze,*pmaze;                   //迷宫数据结构

typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

typedef LinkList LinkStack;     //定义链栈

void InitStack(LinkStack &S)
{//初始化栈
	S=NULL;
}//endInitStack

void DestroyStack(LinkStack &S)
{//销毁栈
	LinkStack p;
	while(S){
		p=S;
		S=S->next;
		delete p;
	}
}//end DestroyStack

bool GetTop(LinkStack S,int &e)
{//获取栈顶元素
	if(!S)return FALSE;
	e=S->data;
	return TRUE;
}//end GetTop

void Push(LinkStack &S,int e)
{//入栈操作
	LinkStack p;
	p=new LNode;
	p->data=e;
	p->next=S;
	S=p;
}//end Push

bool Pop(LinkStack &S,int &e)
{//出栈操作
	LinkStack p;
	if(!S)return FALSE;
	p=S;
	S=S->next;
	e=p->data;
	delete p;
	return TRUE;
}//end Pop

pmaze creatmaze()
{                                             //生成迷宫并获取迷宫元素
	int i,j;
	char ch;
	maze *maze1;
	maze1=new maze[1];
	cout<<"请输入迷宫行数:";
	cin>>maze1->row;                          
	cout<<endl<<"请输入迷宫列数:";
	cin>>maze1->col;                          //输入行数，列数 
	for(i=0;i<maze1->row+2;i++)
	{
		maze1->location[i][0]='#';
		maze1->location[i][maze1->col+1]='#';
	}                                        
	for(j=1;j<maze1->col+1;j++)
	{
		maze1->location[0][j]='#';
		maze1->location[maze1->row+1][j]='#';
	}                                         //生成迷宫围墙
	for(i=1;i<maze1->row+1;i++)
	{
		cout<<"请输入第"<<i<<"行元素"<<endl;
		for(j=1;j<maze1->col+1;j++)
		{   ch=getchar();
			if(ch=='1'||ch=='0'||ch=='e')     //判断数据输入是否正确
			   maze1->location[i][j]=ch;
			else {
				cout<<"第"<<j<<"位数据元素输入错误然后重新输入本行"<<endl;
				i--;
				ch=-1;
				break;                        //输入错误，行数回退，跳出循环
			}
		}
		if(ch!=-1){                           //ch=-1，输入已出错无需判断数据是否过多
		ch=getchar();                         //获取末位数据，判断是否为结束附
		if(ch!='&'){                          //非结束符，数据输入过多
			cout<<"输入数据过多，重新输入此行"<<endl;
			while(ch=getchar()!='&');ch=getchar();//将为使用的无用数据过滤掉，防止其进入下次输入
			i--;}}
		else while(ch=getchar()!='&');ch=getchar();//将为使用的无用数据过滤掉，防止其进入下次输入
	}
	cout<<"输入完毕"<<endl;
	return maze1;
}

void Destroymaze(pmaze maze)
{                                               // 销毁迷宫
	delete maze;
}

void copymaze(pmaze maze1,pmaze maze2)
{                                               //复制maze1至maze2
	int i,j;
	for(i=0;i<maze1->row+2;i++)
		for(j=0;j<maze1->col+2;j++)
			maze2->location[i][j]=maze1->location[i][j];
		maze2->col=maze1->col;
		maze2->row=maze1->row;
}

void outputmaze(pmaze maze)
{                                              //输出迷宫maze
	int i,j;
	for(i=0;i<maze->row+2;i++)
	{
		for(j=0;j<maze->col+2;j++)
			cout<<maze->location[i][j]<<"	";
		cout<<endl;
	}
}

int findway(pmaze maz,LinkStack &path1,LinkStack &path2,int i,int j)
{                                              //寻找maz出路的递归函数，当前坐标为(i，j)，path1用来存出路的横坐标，        
	int c,r,flag,ch,temp1,temp2;               //path2用来存纵坐标
	flag=1;
	ch=0;
	if(maz->location[i][j]=='e')
	{	return TRUE;}                          //当前坐标数据为e，迷宫已走出
	else if(maz->location[i][j+1]=='1'||maz->location[i][j+1]=='e')
	{                                          //试探临近右格
		maz->location[i][j]='@';               //已走过格子数据置@
		Push(path1,i);Push(path2,j);           //坐标进栈
		ch=findway(maz,path1,path2,i,j+1);     //坐标右移一格继续findway
	}
	else if(maz->location[i+1][j]=='1'||maz->location[i+1][j]=='e')
	{                                          //试探临近下格
		maz->location[i][j]='@';
		Push(path1,i);Push(path2,j);
		ch=findway(maz,path1,path2,i+1,j);
	}
	else if(maz->location[i][j-1]=='1'||maz->location[i][j-1]=='e')
	{                                          //试探临近左格
		maz->location[i][j]='@';
		Push(path1,i);Push(path2,j);
		ch=findway(maz,path1,path2,i,j-1);
	}
	else if(maz->location[i-1][j]=='1'||maz->location[i-1][j]=='e')
	{                                          //试探临近上格
		maz->location[i][j]='@';
		Push(path1,i);Push(path2,j);
		ch=findway(maz,path1,path2,i-1,j);
	}
	else {temp1=i;temp2=j;                     //此位置为死路，回退一格，保留此处坐标
	if(Pop(path1,i)){                          //判断是否为栈中第一个元素
			Pop(path2,j);                      //出栈(i,j)变为上次试探坐标
			maz->location[temp1][temp2]='@';   //原死路处数据置@
		ch=findway(maz,path1,path2,i,j);       //坐标回退后继续findway
		}
		else return 0;                         //首元素即为死路，此迷宫无通路
	}
/*	for(c=1;c<maz->row;c++)                    //原为判断迷宫是否有通路，后证明为多余
		for(r=1;r<maz->col;r++);               
		{if(maz->location[c][r]=='@'||maz->location[c][r]=='e'||maz->location[c][r]=='0')
		      flag=0;
		}
		if(flag==1){
			return 0;
				
			}*/
	return ch;
}

void main()
{
	int i=1;
	int j=1;
	int result;
	pmaze maze1,maze2,maze3;              //maze1为操作用迷宫，maze2为保留的原迷宫，maze3用来显示通路在迷宫值得位置
	LinkStack path1,path2;
	path1=new LNode;
	path2=new LNode;
    InitStack(path1);
	InitStack(path2);
	maze1=creatmaze();
	maze2=new maze[1];
	maze3=new maze[1];
	copymaze(maze1,maze2);
	copymaze(maze1,maze3);
	outputmaze(maze1);
	result=findway(maze1,path1,path2,i,j);
	if(!result)
		cout<<"此迷宫无出路"<<endl;
	else{
		Pop(path1,i);
		Pop(path2,j);
		while(i)                         //依次输出迷宫通路坐标(倒序)，并修改maze3中的数据，将迷宫通路上的元素置@
		{
			cout<<"路线各点坐标为:("<<i<<','<<j<<')'<<endl;
			maze2->location[i][j]='*';
			if(!Pop(path1,i)) break;
			Pop(path2,j);
		}
		cout<<"迷宫出路如图:"<<endl;
		outputmaze(maze2);
	}
	cout<<"原迷宫为:"<<endl;
	outputmaze(maze3);
	Destroymaze(maze1);
	Destroymaze(maze2);
	Destroymaze(maze3);
	DestroyStack(path1);
	DestroyStack(path1);                //释放空间
}
用户输入数据时首先输入迷宫行数与列数，然后由程序自动生成迷宫围墙，用户继续依次输入迷宫每行元素，以&为结束符，元素个数必须等于列数且元素必须为0或1或e（只能有一个e为出口），否则程序报错，1为能走同，0为死路，左上角为入口。迷宫输入完毕后由程序自动找到连通入口与出口的路径，程序输出路径各点坐标及标出路径的迷宫图表，程序接着会输出原迷宫以便用户进行对照。