maze.cpp

数据结构课程设计：迷宫

/*
      设计迷宫并求解
朱文波 20058001251 软件一班
*/


# include <iostream.h>
# include "Maze.h"
int Pass(PosType a)
{//当迷宫m的a点的序号为1（表示可通过），返回1，否则返回0
	if(m[a.x][a.y]==1)
		return 1;
	return 0;
}



PosType NextPos(PosType b,int di)
{//根据当前的位置以及移动方向，返回下一位置
	PosType direc[4]={{0,1},{1,0},{0,-1},{-1,0}};//{行增量，列增量}
	//移动方向依次为东南西北，按“左西右东上北下南”规则来移动
	b.x+=direc[di].x;
	b.y+=direc[di].y;
	return b;
}


void FootPrint(PosType c)
{//将迷宫m的a点的序号变为足迹（curstep）
	m[c.x][c.y]=curstep;
}


void MarkPrint(PosType d)
{//将不能通过的路径标为-1
	m[d.x][d.y]=-1;
}


int MazePath(PosType start,PosType end)
{//求迷宫的通路
	SqStack S;
	PosType curpos;
	SElemType e;
	InitStack(S);
	curpos=start;
	do
	{
		if(Pass(curpos))
		{//当前位置可以通过（没有走过的通道块）
			FootPrint(curpos);   //留下足迹
			e.ord=curstep;
			e.seat.x=curpos.x;
			e.seat.y=curpos.y;
			e.di=0;
			Push(S,e);           //入栈，当前位置以及状态
			curstep++;           //足迹加1
			if(curpos.x==end.x&&curpos.y==end.y)
				return 1;        //到达出口  
			curpos=NextPos(curpos,e.di);
		}
		else
		{//当前位置不能通过
			if(!StackEmpty(S))
			{	
				Pop(S,e);        //退栈到前一个位置
				curstep--;
				while(e.di==3&&!StackEmpty(S)) 
				{                //前一个位置的最后一个方向（北）
					MarkPrint(e.seat);//不能通过，留下标记-1
					Pop(S,e);    //退一步
					curstep--;
				}
				if(e.di<3)       //没到最后一个方向
				{
					e.di++;
					Push(S,e);   //换下一个方向
					curstep++;
					curpos=NextPos(e.seat,e.di);//当前的位置为新方向上的相邻块
				}
			}
		}
	}
	while(!StackEmpty(S));
	return 0;
}


void Print(int x,int y)
{//输出迷宫
	int i=0,j=0;
	for(i=0;i<x;i++)
	{
		for(j=0;j<y;j++)
		{
			cout<<m[i][j]<<"\t";
		}
		cout<<endl;
	}
}


void main()
{
	PosType begin,end;
	int i=0,j=0,w=0,x=0,y=0,x1=0,y1=0;
	cout<<"\t\t\t迷宫问题\n\n我们用0代表墙,1代表可走路径";
	cout<<"请输入迷宫的行数，列数(包括外墙)以空格隔开:";
	cin>>x>>y;
	for(i=0;i<x;i++)             //定义行周边值为0(墙)
	{
		m[0][i]=0;        
		m[x-1][i]=0;
	}
	for(j=0;j<y;j++)             //定义列周边值为0(墙)
	{
		m[j][0]=0;        
		m[j][y-1]=0;
	}
	for(i=1;i<x-1;i++)           //定义通道初值为1
	{
		for(j=1;j<y-1;j++)
		{
			m[i][j]=1;
		}
	}
	cout<<"请输入迷宫内部墙的单元数:";
	cin>>j;
	cout<<"依次输入迷宫内部每个墙的所在行数和列数(以空格隔开)(不计外围的墙):\n";
	for(i=1;i<=j;i++)            //定义内部的墙
	{
		cin>>x1>>y1;
		m[x1][y1]=0;
	}
	cout<<"迷宫结构如下:\n";
	Print(x,y);
	cout<<"输入起点位置:所在的行数和列数(以空格隔开)(不计外围的墙)";
	cin>>begin.x>>begin.y;
	cout<<"输入终点位置:所在的行数和列数(以空格隔开)(不计外围的墙)";
	cin>>end.x>>end.y;
	if(MazePath(begin,end))      //求解
	{
		cout<<"迷宫从入口到出口的一条路径如下:\n";
		Print(x,y);              //输出一条路经
	}
	else                         //无解
		cout<<"迷宫无解";
}