C++课程设计：迷宫问题演示程序

答案：#include<stdio.h> 
#include<stdlib.h> 
#include<iostream>
using namespace std;
#define M 15 
#define N 15 
int z=0;
struct Point
{
 int m_1;
 int n_1;
 Point_cout();
 Point_cout1();
};
Point::Point_cout()
{
 return(m_1);
}
Point::Point_cout1()
{
 return(n_1);
}
struct mark //定义迷宫内点的坐标类型 
{ 
int x; 
int y; 
}; 
struct Element  
{ 
int x,y; //x行,y列 
int d; //d下一步的方向 
}; 
typedef struct LStack //链栈 
{ 
Element elem; 
struct LStack *next; 
}*PLStack; 

/*************栈函数****************/ 
int InitStack(PLStack &S)//构造空栈 
{ 
S=NULL; 
return 1; 
} 
int StackEmpty(PLStack S)//判断栈是否为空 
{ 
if(S==NULL) 
return 1; 
else 
return 0; 
} 
int Push(PLStack &S, Element e)//压入新数据元素 
{ 
PLStack p; 
p=(PLStack)malloc(sizeof(LStack)); 
p->elem=e; 
p->next=S; 
S=p; 
return 1; 
} 
int Pop(PLStack &S,Element &e) //栈顶元素出栈 
{ 
PLStack p; 
if(!StackEmpty(S)) 
{ 
e=S->elem; 
p=S; 
S=S->next; 
free(p); 
return 1; 
} 
else 
return 0; 
} 

/***************求迷宫路径函数***********************/ 
void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[2][4][2],int z,int &a,int &b) 
{ 
int m=a;
int n=b;
int i,j,d;
int a_1,b_1;
Element elem; 
PLStack S1, S2; 
InitStack(S1); 
InitStack(S2); 
if(z<2)
{
for(int w_1=0;w_1<9;w_1++)
for(int w_2=0;w_2<8;w_2++)
if(maze[w_1][w_2]==2)
maze[w_1][w_2]=0;
maze[start.x][start.y]=2;
//入口点作上标记 
elem.x=start.x; 
elem.y=start.y; 
elem.d=-1;
Push(S1,elem);  //开始为-1 
//cout<<elem.x<<" "<<elem.y<<" "<<elem.d<<" ";  
while(!StackEmpty(S1)) //栈不为空 有路径可走 
{
Pop(S1,elem); 
//cout<<elem.x<<elem.y<<elem.d;
i=elem.x; 
j=elem.y; 
d=elem.d+1;
while(d<4) //试探东南西北各个方向 
{ 
a_1=i+diradd[z][d][0]; 
b_1=j+diradd[z][d][1]; 
if(a_1==end.x && b_1==end.y && maze[a_1][b_1]==0) //如果到了出口 
{ 
cout<<"可以到达出口的路径有："<<endl;
//maze[a][b]=2 
elem.x=i; 
elem.y=j; 
elem.d=d; 
Push(S1,elem); 
elem.x=a_1; 
elem.y=b_1; 
elem.d=886; //方向输出为-1 判断是否到了出口 
Push(S1,elem); 
//cout<<"\n0=东 1=南 2=西 3=北 886为则走出迷宫\n\n通路为:(行坐标,列坐标,方向)";
cout<<endl;
while(S1) //逆置序列 并输出迷宫路径序列 
{ 
Pop(S1,elem);
//cout<<"("<<e.x<<","<<e.y<<","<<e.d<<")"<<"-->"; 
Push(S2,elem); 
} 
while(S2) 
{ 
Pop(S2,elem); 
printf("-->(%d,%d,%d)",elem.x,elem.y,elem.d); 
} 
cout<<endl;
for(i=0;i<=m+1;i++) //输出迷宫 
{ 
for(j=0;j<=n+1;j++) 
cout<<maze[i][j]<<" "; 
cout<<endl; 
} 
++z;
MazePath(start,end,maze,diradd,z,a,b);
} 
if(maze[a_1][b_1]==0) //找到可以前进的非出口的点 
{ 
maze[a_1][b_1]=2; //标记走过此点 
elem.x=i; 
elem.y=j; 
elem.d=d; 
Push(S1,elem); //当前位置入栈 
i=a_1; //下一点转化为当前点 
j=b_1; 
d=-1; 
} 
d++; 
}
}
//cout<<"("<<elem.x<<","<<elem.y<<","<<elem.d<<")"<<"-->"<<"||";
} 
//cout<<"没有找到可以走出此迷宫的路径\n"; 
} 

/*************建立迷宫*******************/ 
int initmaze(int maze[M][N],int &a,int &b) 
{ 
int i,j; 
int m,n; //迷宫行,列 
cout<<"请输入迷宫的行数 m="; 
cin>>m; 
cout<<"请输入迷宫的列数 n="; 
cin>>n;
a=m;
b=n;
cout<<"请输入迷宫的各行各列:\n用空格隔开,0代表路,1代表墙:"; 
cout<<endl;
for(i=1;i<=m;i++) 
for(j=1;j<=n;j++) 
cin>>maze[i][j]; 
cout<<"你建立的迷宫为:"; 
cout<<endl;
for(i=0;i<=m+1;i++) //加一圈围墙 
{ 
maze[i][0]=8; 
maze[i][n+1]=8; 
} 
for(j=0;j<=n+1;j++) 
{ 
maze[0][j]=8; 
maze[m+1][j]=8; 
} 
for(i=0;i<=m+1;i++) //输出迷宫 
{ 
for(j=0;j<=n+1;j++) 
cout<<maze[i][j]<<" "; 
cout<<endl; 
}
return 0;
} 
void main() 
{
int a=0;
int b=0; 
int sto[M][N]; 
struct mark start,end; //start,end入口和出口的坐标 
int add[2][4][2]={{{0,1},{1,0},{0,-1},{-1,0}},{{1,0},{0,1},{0,-1},{-1,0}}};//行增量和列增量 方向依次为东西南北 
cout<<"注:上面的式子一维为2，根据东西南北，共有16种排列，因数量太多，故省略只写顺序依次为东南西北和南东西北";
cout<<endl;
initmaze(sto,a,b);//建立迷宫 
cout<<"输入入口的横坐标,纵坐标"; 
cin>>start.x>>start.y;
cout<<"输入出口的横坐标,纵坐标"; 
cin>>end.x>>end.y; 
MazePath(start,end,sto,add,z,a,b); //find path 
//system("PAUSE"); 
} 

// 下面是以9行8列的输入（你可以复制，黏贴就ok 了）0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0 0 0 1 1 0 1 1 1 1 0 1 1 0 0 0 0 0 0 1 1 1 0 1 1 1 1 1

上一个：C++与C#的差别有哪些？
下一个：学习c++什么程度才算精通