一、简介
大学期间用vc++开发的简单的迷宫，其中0代表可通1代表不可通。迷宫中主要有二个功能模块，一是用栈保存迷宫通路，二是用队列实现迷宫最短路径。
二、详解
1、前景和后景的颜色控制
system()函数中的cls进行清屏操作保证界面的美观，color进行设置前景和后景的颜色，随时改变颜色，以达到视觉的享受。
2、代码
（1）main.cpp#include<iostream>（2）编译运行
#include<conio.h> //使用getchar()函数，接受任意字符
#include<iomanip> //使用setw()函数设置格式
#include<windows.h> //运用清屏和改变前景和背景颜色
#include<stdlib.h>
#include<time.h> //调用rand()随机生成数组
using namespace std;
#define Max 50 //数组的最大值
int maze[Max][Max]; //迷宫数组
void back();
void Creatmi();//创建迷宫数组函数的声明
void getback()//返回主界面
{
cout<<"按任意键返回"<<endl;
getch();
back();
}
int ai,bi,ci,di;//出口和入口的值
int m,n;// 数组的行和列
void Maze()//定义数组
{
m=8;n=10;//行列的最大值
int i,j;//行列
for(i=0,j=0;j<10;j++)
maze[i][j]=1;
for(i=7,j=0;j<10;j++)
maze[i][j]=1;
for(j=0,i=1;i<7;i++)
maze[i][j]=1;
for(j=9,i=1;i<7;i++)
maze[i][j]=1;
maze[1][1]=0;maze[1][2]=1;maze[1][3]=1;
maze[1][4]=1;maze[1][5]=0;maze[1][6]=1;
maze[1][7]=1;maze[1][8]=1;maze[2][1]=1;
maze[2][2]=0;maze[2][3]=1;maze[2][4]=0;
maze[2][5]=1;maze[2][6]=1;maze[2][7]=1;
maze[2][8]=1;maze[3][1]=0;maze[3][2]=1;
maze[3][3]=0;maze[3][4]=0;maze[3][5]=0;
maze[3][6]=0;maze[3][7]=0;maze[3][8]=1;
maze[4][1]=0;maze[4][2]=1;maze[4][3]=1;
maze[4][4]=1;maze[4][5]=0;maze[4][6]=1;
maze[4][7]=1;maze[4][8]=1;maze[5][1]=1;
maze[5][2]=0;maze[5][3]=0;maze[5][4]=1;
maze[5][5]=1;maze[5][6]=0;maze[5][7]=0;
maze[5][8]=0;maze[6][1]=0;maze[6][2]=1;
maze[6][3]=1;maze[6][4]=0;maze[6][5]=0;
maze[6][6]=1;maze[6][7]=1;maze[6][8]=0;//自带数组初始化
}
#define MAXSIZE 100
typedef struct //move数组定义
{
int x1;int y1;
}item;
item moveItem[8]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
typedef struct//栈中三元组
{
int x,y,d;
}DataType;
typedef struct//栈中要存储的元素
{
int a,b,c;
}stack;
typedef struct
{
stack data[MAXSIZE];//栈的数组和指针
int top;
}SeqStack;
void Init_SeqStack(SeqStack*s)//栈初始化
{
if(!s)
{cout<<"空间不足!"<<endl;
return;
}
else
s->top=-1;
}
int Empty_SeqStack(SeqStack*s)//判断栈是否为空
{
if(s->top==-1)
return 1;
else
return 0;
}
int Push_SeqStack(SeqStack*s,DataType*temp)//入栈操作
{
if(s->top==MAXSIZE-1)
return 0;
else
{
s->top++;
s->data[s->top].a=temp->x;
s->data[s->top].b=temp->y;
s->data[s->top].c=temp->d;//数据入栈
return 1;
}
}
int Pop_SeqStack(SeqStack*s,DataType*temp)//出栈
{
if(Empty_SeqStack(s))
return 0;
else
{
temp->x=s->data[s->top].a;
temp->y=s->data[s->top].b;
temp->d=s->data[s->top].c;
s->top--;
return 1;
}
}
int path(SeqStack*s)//用栈实现迷宫的解
{
Creatmi();int i,j;
DataType*temp=new DataType;//申请空间
int x2,y2,d2;
cout<<"请输入入口坐标:";cin>>ai>>bi;
cout<<"请输入出口坐标:";cin>>ci>>di;
if(maze[ai][bi]==1)
{cout<<"无出路!"<<endl;
cout<<"按任意键返回"<<endl;
getch();
}
else
{temp->x=ai;//第一个点的入栈
temp->y=bi;
temp->d=-1;
maze[ai][bi]=1;
Push_SeqStack(s,temp);
while(!Empty_SeqStack(s))
{
Pop_SeqStack(s,temp);
x2=temp->x;
y2=temp->y;
d2=temp->d+1;
while(d2<8)
{
i=x2+moveItem[d2].x1;//调用move数组从八个方位搜索
j=y2+moveItem[d2].y1;
if(maze[i][j]==0)
{
temp->x=x2;
temp->y=y2;
temp->d=d2;
Push_SeqStack(s,temp);//进入栈中
x2=i;
y2=j;
maze[x2][y2]=-1;
if(x2==ci&&y2==di)//无出路
return 1;
else
d2=0;
}
else
d2++;
}
}
}
if(s->top==-1)//栈中无元素
{
cout<<"此迷宫无路径!"<<endl;
cout<<"无出路!"<<endl;
cout<<"按任意键返回"<<endl;
getch();
path(s);
}
return 0;
}
void Creatmi()//创建数组
{
system("cls");//清屏 DOC调用
system("color 2F"); //颜色 调用doc
int j;
cout<<"*****0、返回主菜单. "<<" 1、自己输入新的数组."<<endl;
cout<<"******2、用函数随机生成数组. "<<"3、调用自带的数组."<<endl;
cout<<"请输入操作选择:";
cin>>j;
if(j>3||j<0) //输入超出范围控制
{
cout<<"输入有误!"<<endl;
Creatmi();//返回
}
switch(j)
{
case 1:{cout<<"请输入数组的大小(一维和二维)!"<<endl;//手动输入数组
cin>>m>>n;
cout<<"请输入数组元素!(从(0,0)开始)!"<<endl;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
cin>>maze[i][j];}
break;
case 2:{srand(time(0));int i,j;
cout<<"请输入数组(包括外围大小)的大小(一维和二维)!"<<endl;
cin>>m>>n;
for(i=0,j=0;j<n;j++)//随机生成数组
maze[i][j]=1;
for(i=m-1,j=0;j<n;j++)
maze[i][j]=1;
for(j=0,i=1;i<m-1;i++)
maze[i][j]=1;
for(j=n-1,i=1;i<m-1;i++)
maze[i][j]=1;
for( i=1;i<m-1;i++)
for( j=1;j<n-1;j++)
maze[i][j]=rand()%2;
}
break;
case 3:Maze();break;
case 0:getback();break;
default:cout<<"你的输入有误!\n";break;
}
cout<<"创建的数组(包括外围大小)为:"<<endl;
for(int i=0;i<m;i++)
{
for( j=0;j<n;j++)
cout<<maze[i][j]<<" ";
cout<<endl;
}
}
void prinkpath(SeqStack*s)//输出栈中保存的通路
{
cout<<"栈中保存的一条迷宫通路是:"<<endl;
cout<<"("<<ci<<","<<di<<")";
for(int i=s->top;i>=0;i--)
cout<<"<--("<<s->data[i].a<<","<<s->data[i].b<<")";
cout<<endl;
}
typedef struct
{
int x,y;//通路中数组的下标
int pre;//结点的前驱指针
}SqType;
SqType sq[MAXSIZE];
int front,rear;
void printpath2()//输出队列中的最短迷宫通路
{
int i;
i=rear;
cout<<"队列中保存的最短迷宫通路是:"<<endl;
do
{cout<<"("<<sq[i].x<<","<<sq[i].y<<")<--";
i=sq[i].pre;
}while(i!=0);
cout<<"("<<ai<<","<<bi<<")"<<endl;
}
void path2()//最短迷宫通路的求解
{
Creatmi();
int x,y,i,j,v;
front=rear=0;
cout<<"请输入入口坐标:";cin>>ai>>bi;
cout<<"请输入出口坐标:";cin>>ci>>di;
if(maze[ai][bi]==1||maze[ci][di]==1)
cout<<"无出路!"<<endl;
else//探求最短路径
{sq[0].x=ai;
sq[0].y=bi;
sq[0].pre=-1;
maze[ai][bi]=-1;
while(front<=rear)//入队
{
x=sq[front].x;
y=sq[front].y;
for(v=0;v<8;v++)
{
i=x+moveItem[v].x1;//move数组调用
j=y+moveItem[v].y1;
if(maze[i][j]==0)
{
rear++;
sq[rear].x=i;
sq[rear].y=j;
sq[rear].pre=front;
maze[i][j]=-1;
}
if(i==ci&&j==di)
{
printpath2();//输出
cout<<"按任意键返回"<<endl;
getch();
path2();
return;
}
}
front++;
}
if(i!=ci&&j!=di)
cout<<"此迷宫路径上无最短路径!"<<endl;
}
cout<<"按任意键返回"<<endl;
getch();
path2();//返回上级界面
}
void back()//进入迷宫操作
{
system("cls");//清屏 DOC调用
system("color 2F"); //颜色 调用doc
SeqStack *s=new SeqStack;
cout<<"0、退出. "<<"1、用栈保存迷宫通路. "<<"2、用队列实现迷宫最短路径."<<endl;
cout<<"请输入操作选择:";
int j;
cin>>j;
if(j>3||j<0) //输入超出范围控制
{
cout<<"输入有误!"<<endl;
getback();
}
switch(j)
{
case 1:Init_SeqStack(s);path(s);prinkpath(s);getback();break;
case 2:path2();
break;
case 0:exit(0);break;
default:cout<<"你的输入有误!\n";break;
}
}
int _tmain(int argc, _TCHAR* argv[]) //主函数
{
system("cls");//清屏 DOC调用
system("color 1F"); //颜色 调用doc
cout<<setw(45)<<"您想进入实现迷宫系统?"<<endl;
cout<<"若进入请按Y，若不进入请按N."<<endl;
char a;
cin>>a;
if(a=='Y'||a=='y')
back();
return 0;
}
在vc6.0或vs2010上都能编译通过（用自带的相同的数组来体现栈和队列所保存的迷宫通路的不同）：
三、总结
（1）上述代码仅仅用来回忆学习C++的过程。（2）若有建议，请留言，在此先感谢！