#include<iostream>
#include<stack>
#include<stdio.h>
#include<time.h>
#include<string>
using namespace std;
typedef struct
{
int x,y;
}item;
typedef struct
{
int x,y,d;
}Datetype;
typedef stack<Datetype> stack_int;
void path (int **maze,int,int,int,int);
void printpath();
#define NUM 100    //队列大小；
typedef struct{
int x,y;  //所到点的坐标；
int pre;  //前驱点的下标；
}SqType;  //队列；
int front,rear;  //队首指针与队尾指针；
游戏免费源码分享网站void printpath(SqType sq[],int){//打印路径
int i;
i=rear;
do{
cout<<"("<<sq[i].x<<","<<sq[i].y<<")<--";
i=sq[i].pre;  //回溯；
}while(i!=-1);
}
void restore(int **maze,int m,int n){//恢复迷宫
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(maze[i][j]==-1)
maze[i][j]=0;
}
}
}
int path1(int **maze,int m,int n,int c,int d,int x1,int y1)//最短路径
{  //m,n为迷宫的长和宽，c，d为迷宫入口坐标，x1，y1为迷宫出口坐标；maze为迷宫；
item move[8]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};  //坐标增量数组；
SqType sq[NUM];
int x,y,i,j,v; 
front=rear=0;
sq[0].x=c;
sq[0].y=d;
sq[0].pre=-1;
if(maze[c][d]==0)
maze[c][d]=-1;//入口点入队；
else goto G;
while(front<=rear){    //队列不为空
x=sq[front].x;
y=sq[front].y;
for(v=0;v<8;v++){
i=x+move[v].x;
j=y+move[v].y;
if(maze[i][j]==0){
rear++;
sq[rear].x=i;
sq[rear].y=j;
sq[rear].pre=front;
maze[i][j]=-1; //访问过的坐标点，入队；
}
if(i==x1&&j==y1){
cout<<"最短路径为："<<endl;
printpath(sq,rear);  //输出路径；
restore(maze,m,n);    //恢复迷宫；
return 1;
}
}  //for v;
front++;  //当前点搜索完，取下一个点搜索
}  //while
G:cout<<"无路径。"<<endl;
return 0;
}
void path(int **maze,int a,int b,int m,int n)
{
item move[8]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
stack_int st;
Datetype temp;
int x,y,d,i,j;
if(maze[a][b]==1){cout<<"进口输入有误。";return;}
temp.x=a;temp.y=b;temp.d=-1; //初始化入口点坐标及方向；
st.push(temp);
while(!st.empty())
{
p();
st.pop();
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; //坐标及方向；
st.push(temp); //坐标及方向入栈；
x=i;y=j;
maze[x][y]=-1;//到达新点；
if(x==m && y==n)
{
cout<<" 迷宫路径为:"<<endl;
cout<<"("<<m<<","<<n<<")<---";
Datetype t;
while(!st.empty())
{
p();
cout<<"("<<t.x<<","<<t.y<<")<---";
st.pop();
}    //输出路径；
cout<<endl;
return ;  //到达出口；
}
else d=0;  //重新初始化方向；
}
else d++;    //改变方向；
}
}
cout<<"对不起，无法到
出口.";
return;  //迷宫无路；
}
void printpath()
{
int m,n,i,j,l,c,d;
string s;
cout<<"********************************************************************************\n"<<endl;
cout<<"                              欢迎进入迷宫求解系统\n"<<endl;
cout<<"********************************************************************************\n"<<endl;
cout<<"    请输入迷宫的行数:"<<endl;
cin>>m;
cout<<"    请输入迷宫的列数:"<<endl;
cin>>n;
int **maze=new int*[m+2];
for(i=0;i<=m+1;i++)
maze[i]=new int[n+2];//申请迷宫的空间；
for(i=0;i<=m+1;i++) 
maze[i][0]=1;
for(i=0;i<=n+1;i++)
maze[0][i]=1;
for(i=0;i<=m+1;i++)
maze[i][n+1]=1;
for(i=0;i<=n+1;i++)
maze[m+1][i]=1;  //建立迷宫周围的墙；
cout<<"********************************************************************************\n"<<endl;
cout<<"  ☆  自动生成迷宫  请按：1\n  ☆  手动生成迷宫  请按：2\n"<<endl;
cout<<"********************************************************************************\n"<<endl;
cin>>s;
if(s=="1")
{
srand(time(0));  //系统时间随机函数；
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
maze[i][j]=rand()%2;  //随机赋值
maze[1][1]=0;  //(1,1)点为可通过点；
maze[m][n]=0;  //(m,n)点为可通过点；
}
else
{
cout<<"请输入迷宫："<<m<<"行"<<n<<"列"<<", 输入必须为'0' 或 '1'；"<<endl;
for(i=1;i<=m;i++)    //输入第i行迷宫的构造；
for(j=1;j<=n;j++)    //输入第j列迷宫的结构；
{
cin>>maze[i][j];
A:if(maze[i][j]!=0 && maze[i][j]!=1)
{
cout<<"请再次输入：";
cin>>maze[i][j];goto A;  //判错；
}
}
}
cout<<"迷宫如下："<<endl; //显示用户输入的迷宫；
for(i=0;i<=m+1;i++)
{
for(j=0;j<=n+1;j++)
{
if (*(maze[i]+j)==0||*(maze[i]+j)==5)
{
cout<<"  ";
}
else if(*(maze[i]+j)==1)
{
cout<<"□";
}
else if(*(maze[i]+j)==2)
{
cout<<"※";
}
else if(*(maze[i]+j)==3)
{
cout<<"■";
}
else if(*(maze[i]+j)==4)
{
cout<<"☆";
}
else if(*(maze[i]+j)==6)  //到出口标识
{
cout<<"★";
}
else
{
cout<<"出错!";   
}
}
cout<<"\n";
}
H:cout<<"请输入迷宫入口(a,b)，出口(c,d)：";
cin>>i>>j>>c>>d;
path(maze,i,j,c,d);    //调用路径函数，输出路径；
cout<<endl;  //格式设置；
restore(maze,m,n);  //恢复迷宫；
path1(maze,m,n,i,j,c,d);  //输出最短路径；
cout<<endl;  //格式设置；
cout<<"********************************************************************************\n";
cout<<"  1、寻其他入口与出口；\n  2、退出此迷宫；\n";
cout<<"********************************************************************************\n";
cin>>l; 
if(l==1){
restore(maze,m,n);  //恢复迷宫；
goto H;
}
else return;  //跳出此函数；
}
void main()
{
string s="Y";
do
{
cout<<"--------------------------欢迎到达迷宫界面--------------------------\n";
printpath();
cout<<endl;
cout<<"\n 是否继续？'Y' 或'N'（输入其他操作按'N'）"<<endl;
cin>>s;
}while (s=="Y"||s=="y");
system("pause");
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。