maze.cpp

数据结构的迷宫求解

#include<iostream>
#include<time.h>
#include"Base.h"
using namespace std;


/////////////////////////////////////////////main函数////////////////////////////////////////////
int main()
{
	int com;bool f=true;char str='r';
	MazeType M;PosType start,end;
	start.r=start.c=1;
	end.r=end.c=RANGE;
	InitMaze(M);
	do
	{
		cout<<"  ****************************************************************************"<<endl;
		cout<<"  *             1演示          2建迷宫         3求迷宫通路         4退出     *"<<endl;
		cout<<"  ****************************************************************************"<<endl;
		cin>>com;
		if(com==1)
			ShowMaze(M);
		if(com==2)
			CreatMaze(M);
		if(com==3)
		{

			cout<<"【请输入迷宫的入口坐标和出口坐标(如“1 1 9 9”)】"<<endl;
			cin>>start.r>>start.c>>end.r>>end.c;
			f=MazePath(M,start,end);
			if(f==false)
				cout<<"【该迷宫不存在通路】"<<endl;
			PrintMaze(M);
		}
		if(com==4)
		{
			cout<<"【确定退出:是|Y，否|N】"<<endl;
			cin>>str;
		}
	}while(str!='Y'&&str!='y');
	cout<<"【谢谢使用！】"<<endl;
	return 0;
}

///////////////////////////////////////////函数定义//////////////////////////////////////////////
//迷宫函数
void InitMaze(MazeType &M)//初始化迷宫M，自定义生成一个迷宫
{
	int i,j;
	M.m=M.n=RANGE;
	for (i=0;i<RANGE+2;i++)
	{
		for(j=0;j<RANGE+2;j++)
		{
			if(i==0||i==RANGE+1||j==RANGE+1||j==0)
				M.arr[i][j]='8';
			else
				M.arr[i][j]='0';
		}
	}

}
void ShowMaze(MazeType &M)//演示迷宫
{
	cout<<"【这是随机生成的一个迷宫，迷宫中空白表示未探测路径，】"<<endl;
	cout<<"【'#'表示障碍，'@'表示死胡同，'>'表示所求路径       】"<<endl;
	cout<<"【图中的默认入口为:(1，1);默认出口为:(10,10)        】"<<endl;
	int i,j;PosType start,end;
	start.r=start.c=1;
	end.c=end.r=RANGE;
	M.m=M.n=RANGE;
	srand((unsigned)time(NULL));
	for(i=1;i<RANGE+1;i++)
		for(j=1;j<RANGE+1;j++)
		{
			if(rand()%4==0)
				M.arr[i][j]='1';
			else
				M.arr[i][j]='0';
		}
	bool f=MazePath(M,start,end);
	PrintMaze(M);
	if(f==false)
		cout<<"【该迷宫不存在通路】"<<endl;
}

void CreatMaze(MazeType &M)//用户输入迷宫
{
	int i,j;	
	cout<<"【请输入迷宫的行列数】:"<<endl;
	cin>>M.m>>M.n;
	cout<<"【请以文件(即输入01……系列)形式输入迷宫，输入0表示迷宫无障碍，1表示障碍】"<<endl;
	for(i=1;i<=M.m;i++)
	{
		for(j=1;j<=M.n;j++)
			cin>>M.arr[i][j];
		M.arr[i][M.n+1]='8';
	}
	for(i=M.m+1,j=1;j<=M.n;j++)
		M.arr[i][j]='8';
	M.arr[i][M.n+1]='8';
	cout<<"【迷宫已创建】-》可以执行第3步"<<endl;
}
bool MazePath(MazeType &M,PosType start,PosType end)//找出一条迷宫路径
{
	PosType curpos;Stack S;ElemType e;
	int curstep=1;//探索第一步
	curpos=start;
	InitStack(S);
	do
	{
		if(Pass(M,curpos))//当前位置可以通过，即是未曾走过的通道块
		{
			FootPrint(M,curpos);//留下足迹
			e.step=curstep;e.seat=curpos;e.di=1;
			Push(S,e);//加入路径
			if(curpos.c==end.c&&curpos.r==end.r)
				return(true);
			curpos=NextPos(curpos,1);//下一个位置是当前位置的东邻
			curstep++;//探索下一步
			
		}//if
		else
		{
			if(!StackEmpty(S))
			{
				Pop(S,e);
				while(e.di==4&&!StackEmpty(S))
				{
					MarkPrint(M,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));
	return(false);
}//MazePath
//定义内置函数
bool Pass(MazeType M,PosType t)//当前位置可以通过
{
	if(M.arr[t.r][t.c]=='0')return true;
	else return false;
}
void FootPrint(MazeType &M,PosType t)//留下足迹
{
	M.arr[t.r][t.c]='*';
}
void MarkPrint(MazeType &M,PosType t)//不通过标记
{
	M.arr[t.r][t.c]='@';
}
PosType NextPos(PosType t,int k)//下一个相邻块
{
	PosType str;
	if(k==1)
	{
		str.c=t.c+1;str.r=t.r;
	}
	if(k==2)
	{
		str.r=t.r+1;str.c=t.c;
	}
	if(k==3)
	{
		str.c=t.c-1;str.r=t.r;
	}
	if(k==4)
	{
		str.r=t.r-1;str.c=t.c;
	}
	return str;
}
void PrintMaze(MazeType M)//输出迷宫
{
	int i,j;
	for(i=0;i<M.m+2;i++)
	{
		for(j=0;j<M.n+2;j++)
		{
			switch(M.arr[i][j])
			{
			case '1':cout<<" #";break;
			case '0':cout<<"  ";break;
			case '*':cout<<" >";break;
			case '@':cout<<" @";break;
			case'8':cout<<" 8";break;
			default:break;
			}
		}
		cout<<endl;
	}//for
}

//栈函数
inline int InitStack(Stack &S)//初始化栈
{
	S.top=new LNode;
	if(!S.top)exit(OVERFLOOW);
	S.top->next=NULL;
	S.size=0;
	return OK;
}
int Push(Stack &S,ElemType e)//入栈
{
	LinkStack p;
	p=new LNode;
	if(!p)exit(OVERFLOOW);
	p->data.step=e.step;
	p->data.seat=e.seat;
	p->data.di=e.di;
	p->next=S.top->next;
	S.top->next=p;
	S.size++;
	return OK;
}
int Pop(Stack &S,ElemType &e)//出栈
{
	
	if(!StackEmpty(S))
	{
		LinkStack p;
		e.di=S.top->next->data.di;
		e.seat.r=S.top->next->data.seat.r;
		e.seat.c=S.top->next->data.seat.c;
		e.step=S.top->next->data.step;
		p=S.top->next;S.top->next=S.top->next->next;
		delete p;
		S.size--;
		return OK;
	}
	return ERROR;
}
bool StackEmpty(Stack S)//若栈为空，则返回TRUE，否则返回FALSE
{
	if(S.top->next==NULL)
		return true;
	else return false;
}