maze.cpp

这是一个简单的迷宫

#include<iostream.h>
///////////////////////////////////////////
////////    maze数组初始负值    ///////////
const int m=6;  //迷宫的大小
const int n=8;  //迷宫的大小
int maze[m+2][n+2];  //全局变量
void Init_maze();  //初始化迷宫(maze数组)
void xitong_fuzhi();  //系统初始化迷宫
void maze_fuzhi(int p[m+2][n+2]);  //二维数组负值
void show_maze();  //显示迷宫
void Init_maze()      
{
	int a;
	cout<<"1. 调用本系统默认迷宫  0. 自己输入迷宫";
	cout<<"请选择: ";
	cin>>a;
	while(a<1||a>1){
		cout<<"输入有误，请重新输入: ";
		cin>>a;
	}
	if(a==1)xitong_fuzhi();
	else{
		cout<<"该迷宫为6行8列"<<endl;
		cout<<"0表示通路,1表示不通,其他输入默认为不通（包括不输入）";
		for(int i=1;i<=m;i++){
			cout<<"请输入第"<<i<<"行: ";
			for(int j=1;j<=n;j++){
				cin>>maze[i][j];
				while(maze[i][j]<0||maze[i][j]>1)
					maze[i][j]=1;
			}
		}
		for(int q=0;q<10;q++)maze[0][q]=1;
		for(int j=0;j<10;j++)maze[7][j]=1;
		for(int a=1;a<7;a++)maze[a][0]=1;
		for(int k=1;k<7;k++)maze[k][9]=1;
	}
}
void xitong_fuzhi(){  //系统初始化迷宫
	int example_maze[m+2][n+2]=
	{{1,1,1,1,1,1,1,1,1,1}
    ,{1,0,1,1,1,0,1,1,1,1}
	,{1,1,0,1,0,1,1,1,1,1}
	,{1,0,1,0,0,0,0,0,1,1}
    ,{1,0,1,1,1,0,1,1,1,1}
	,{1,1,0,0,1,1,0,0,0,1}
	,{1,0,1,1,0,0,1,1,0,1}
	,{1,1,1,1,1,1,1,1,1,1}};
	maze_fuzhi(example_maze);
}
void maze_fuzhi(int p[m+2][n+2])//数组赋值
{
	for(int i=0;i<m+2;i++)
	    for(int j=0;j<n+2;j++)
		maze[i][j]=p[i][j];
}
void show_maze()
{
	cout<<"0表示通路,1表示不通. 迷宫为:"<<endl;
	for(int i=0;i<6;i++)
	{
		for(int j=0;j<8;j++)
			cout<<maze[i+1][j+1]<<" ";
		cout<<endl;
	}
}
/////////////////////////////////////////
///////     方向数组初始化       ////////
typedef struct
//下一位置的方向
{
    int x;
    int y;
}item;
item move[8];  //方向数组
void Init_move(); //方向数组初始化
void Init_move()
{
	move[0].x=0;move[0].y=1;
    move[1].x=1;move[1].y=1;
	move[2].x=1;move[2].y=0;
	move[3].x=1;move[3].y=-1;
	move[4].x=0;move[4].y=-1;
	move[5].x=-1;move[5].y=-1;
	move[6].x=-1;move[6].y=0;
	move[7].x=-1;move[7].y=1;
};
/////////////////////////////////////////
/////       栈的生成及操作       ////////
const int MAXSIZE=20;  //栈的元素最大数量 
typedef struct
{ 
    int x,y,d;  //横纵座标及方向
}DataType;
typedef struct
//栈,存放已到位置
{
    DataType data[MAXSIZE];
    int top;
}SeqStack;
void Init_SeqStack(SeqStack * s)//为什么不能用(SeqStack s)
//栈的初始化
{
	s->top=-1;
}
void Push_SeqStack(SeqStack * s,DataType temp)
//将temp入栈
{
	s->top++;
    s->data[s->top].x=temp.x;
	s->data[s->top].y=temp.y;
	s->data[s->top].d=temp.d;
}
void Pop_SeqStack(SeqStack * s,DataType & temp)
//将栈顶元素出栈并传植到&temp
{
	temp.x=s->data[s->top].x;
	temp.y=s->data[s->top].y;
    temp.d=s->data[s->top].d;
	s->top--;
}
/////////////////////////////////////////////
//////         查找通路            //////////
void road_show(SeqStack * p);//输出路径  
int path(SeqStack * p)  //路径查找
{
	DataType temp;   //中转变量
	int x,y,d,i,j;
	temp.x=1;
	temp.y=1;
	temp.d=-1;
	Init_SeqStack(p);   //初始化栈
	Push_SeqStack(p,temp);  //temp入栈
	while(p->top!=-1)
	{
		Pop_SeqStack(p,temp);   //以(temp.x,temp.y)为当前基准点
		x=temp.x;
		y=temp.y;
		d=temp.d+1;
		while(d<8)   //试探各个方向
		{
			i=x+move[d].x;
			j=y+move[d].y;
			if(maze[i][j]==0)
			{
				temp.x=x;
				temp.y=y;
				temp.d=d;
				Push_SeqStack(p,temp);
				x=i;
				y=j;
				maze[x][y]=-1;
				if(x==m&&y==n)
					return 1;  //找到路径
				else d=0;
			}
			else d++;
		}
	}
	return 0;
}
void road_show(SeqStack * p)  
{
    for(int i=0;i<p->top;i++)
	{
		cout<<"("<<p->data[i].x<<","<<p->data[i].y;
		cout<<")"<<"->";
		if(i%5==4)cout<<endl;
    }
	cout<<"("<<"6,8"<<")"<<endl;
}
void Search_Result(SeqStack * p)  //寻找结果(通路是否存在)
{
	int r=path(p);
	switch(r)
	{
	case 1:{
		       cout<<"迷宫通路存在:"<<endl;
			   road_show(p);
		   };return;
	case 0:cout<<"迷宫通路不存在"<<endl;
	}
}
void user_choice(SeqStack * p)
{
	int w=1;
	while(w){
	cout<<"1. 建立（重建）迷宫          2. 显示迷宫"<<endl;
    cout<<"3. 查看是否有通路并显示显示　0. 退出系统"<<endl;
	cout<<"请选择：";
	cin>>w;
	while(w<0||w>3){
		cout<<"输入有误，请重新输入: ";
		cin>>w;
	}
	switch(w){
	case 1:Init_maze();break;
	case 2:show_maze();break;
	case 3:Search_Result(p);break;
	default:break;
	}
	}
}
/////////////////////////////////////////////////////
////////                main()               ////////
void main()
{
	SeqStack s;
	SeqStack * p=& s;
	xitong_fuzhi();
	Init_move();
	user_choice(p);
}