迷宫程序源代码
- 格式：doc
- 大小：35.50 KB
- 文档页数：4
#include"stdio.h"
#include"stdlib.h"
#define M1 11
#define N1 11 /*M1*N1为加上围墙后的迷宫大小*/
#define MAX 100 /*定义栈的最大长度*/
int M=M1-2;
int N=N1-2; /*M*N为原迷宫大小*/
typedef struct /*定义栈元素的类型*/
{
int x,y,dir;
}elemtype;
typedef struct /*定义顺序栈*/
{
elemtype stack[MAX];
int top;
}P;
struct moved /*定义方向位移数组的类型*/
{
int dx;
int dy;
};
void Newmg(int mg[M1][N1]) /*迷宫的初始化*/
{
int i,j,num;
printf("迷宫：\n");
for (i=1;i<=M;i++)
{
for (j=1;j<=N;j++)
{
num=(800*(i+j)+1500)%327; /*根据N和M值伪随机产生迷宫*/
if((num<150)&&(i!=M||j!=N))
mg[i][j]=1;
else
mg[i][j]=0;
printf("%3d",mg[i][j]);} /*输出迷宫*/
printf("\n");
}
printf("\n");
for(i=0;i<=M+1;i++) /*设置迷宫的围墙*/
{
mg[i][0]=1;
mg[i][N+1]=1;
}
for(j=0;j<=N+1;j++) {
mg[0][j]=1;
mg[N+1][j]=1;
}
}
void Newmove(struct moved move[8]) /*定义存储坐标变量的方向位移*/
{
move[0].dx=0;move[0].dy=1; /*寻找方向依次为:东，东南，南，
move[1].dx=1;move[1].dy=1; 西南，西，西北，北，东北*/
move[2].dx=1;move[2].dy=0;
move[3].dx=1;move[3].dy=-1;
move[4].dx=0;move[4].dy=-1;
move[5].dx=-1;move[5].dy=-1;
move[6].dx=-1;move[6].dy=0;
move[7].dx=-1;move[7].dy=1;
}
void Newstack(P *s) /*初始化栈*/
{
s->top=-1;
}
int RuZhan(P *s ,elemtype x) /*将数据元素x压入指针s所指的栈中*/
{
if (s->top==MAX-1)
return (0); /*如栈满，即压栈失败，则返回0*/
else
{
s->stack[++s->top]=x;
return(1); /*压栈成功，则返回1*/
}
}
elemtype ChuZhan(P *s) /*栈顶元素出栈*/
{
elemtype elem;
if (s->top<0) /*如果栈空，返回空值*/
{
elem.x=NULL;
elem.y=NULL;
elem.dir=NULL;
return(elem);
}
else {
s->top--;
return(s->stack[s->top+1]); /*如果栈非空，返回栈顶元素*/
}
}
void Search(int mg[M1][N1],struct moved move[8],P *s)
{ /*寻找迷宫的通路*/
int i,j,dir,x,y,k;
elemtype elem;
i=1;j=1;dir=0;
mg[1][1]=-1; /*设置（1，1）为入口处*/
do
{
x=i+move[dir].dx; /*寻找下一步可行的到达点的坐标*/
y=j+move[dir].dy;
if(mg[x][y]==0)
{
elem.x=i;elem.y=j;elem.dir=dir;
k=RuZhan(s,elem); /*如果可通过，将此点数据压栈*/
if(k==0)
printf("栈长度太短\n"); /*如果入栈操作返回0，说明栈容量不够*/
i=x;j=y;dir=0;mg[x][y]=-1;
}
else if(dir<7)
dir++;
else /*如果八个方向都不可行，就退回一步*/
{
elem=ChuZhan(s);
if (elem.x!=NULL)
{
i=elem.x;
j=elem.y;
dir=elem.dir+1;
}
}
}while (!((s->top==-1)&&(dir>=7)||(x==M)&&(y==N)));
/*循环，直到入口处或出口处为止*/
if(s->top==-1) /*如果最终是入口处，则迷宫无通路*/
printf("此迷宫无通路\n");
else
{
elem.x=x;elem.y=y;elem.dir=dir;
k=RuZhan(s,elem); /*将最后出口的坐标压入栈中*/
printf("迷宫通路：\n"); printf (" 入口->");
i=0;
while (i<=s->top)
{
printf("(%d,%d)->",s->stack[i].x,s->stack[i].y); /*显示迷宫通路*/
if(i!=s->top)
if((i+1)%4==0)
printf("\n");
i++;
}
printf ("出口\n");
}
}
void main() /*寻找迷宫通路程序*/
{
P *s;
int mg[M1][N1];
struct moved move[8];
Newmg (mg); /*调用函数初始化迷宫*/
s=(P*)malloc(sizeof(P));
Newstack(s); /*调用函数初始化栈*/
Newmove(move); /*调用函数初始化位移数组*/
Search (mg,move,s); /*调用函数寻找迷宫通路*/
}
