#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define M 10
#define N 10
#define maxsize 100
int map[M+2][N+2];
int m,n;
typedef struct //试探方向0,1,2,3分别表示东、南、西、北四个方向
{
int x,y;
}item;
item move[4]={{0,1},{1,0},{0,-1},{-1,0}};
typedef struct//栈元素设计
{
int x,y,d;
}datetype;
typedef struct//栈
{
datetype data[maxsize];
int top;
}SeqStack;
SeqStack *s;
SeqStack *Init_SeqStack()//置空栈
{
SeqStack *s;
s=(SeqStack *)malloc(sizeof (SeqStack));
s->top=0;
return s;
}
int Empty_SeqStack(SeqStack *s)//判栈空
{
if (s->top==0) return 1;
else
return 0;
}
int Push_SeqStack(SeqStack *s, datetype x) //入栈
{
if (s->top ==maxsize-1) return 0;
else
{ s->top++;
s->data[s->top]=x;
return 1;
}
}
int Pop_SeqStack(SeqStack *s,datetype x) //出栈
{
if (s->top == 0) return 0;
else
{
x=s->data[s->top];
s->top--;
return 1;
}
}
int path(SeqStack *s) //探索路径
{
datetype temp;
int x,y,d,i,j;
temp.x=1; temp.y=1; temp.d=-1; //设置第一步的位置是(1,1),方向不确定
Push_SeqStack (s,temp); //将第一步放入栈中
while (!Empty_SeqStack(s)) // 当栈不为空,若栈空,则说明更本就没有迷宫
{
x=temp.x; //设定当前位置,当前位置一定是可通的 第一次temp是(1,1,0)
y=temp.y;
d=temp.d+1;
while (d<4) //试探四个方向
{
i=x+move[d].x;
j=y+move[d].y;
if (map[i][j]==0) //如果该方向上可通,则入栈
{
temp.x=i;
temp.y=j;
temp.d=d;
Push_SeqStack(s,temp);
map[x][y]=1; //并把该位置标记为已经走过
x=i; y=j; //把该位置设定为当前位置
if (x==m&&y==n) return 1;
else
d=0;
}
else d++;
}
Pop_SeqStack (s,temp); //若四个方向都走不通,则出栈
}
return 0;
}
void print(SeqStack *s)//输出栈
{
int i;
for (i=1; i<s->top; i++)
{
printf("{[%d,%d],%d}",s->data[i].x, s->data[i].y, s->data[i+1].d);
if (i<s->top ) printf("-->");
if (i%4==0) printf("\n");
}
printf("{[%d,%d]}",s->data[s->top].x, s->data[s->top].y);
printf("\n");
}
void main()
{int i,j,k,h;
printf("请输入迷宫的大小m,n:");
scanf("%d,%d",&m,&n);
srand(time(0));
for (i=0;i<m+2;i++)
for (j=0;j<n+2;j++)
{ if (i==0||i==m+1||j==0||j==n+1) //给迷宫设置外围墙
map[i][j]=2;
else
if ((i==1 && j==1)||(i==m && j==n)) //给迷宫设置出口和入口
map[i][j]=0;
else
{
h=rand()%3; //其他位置随机生成0或1
if (h==2) map[i][j]=1;
else map[i][j]=0;
}
}
printf("新生成的迷宫是:\n");
for (i=0; i<m+2; i++) //打印生成的迷宫
{
for (j=0; j<n+2; j++)
printf("%2d",map[i][j]);
printf("\n");
}
s=Init_SeqStack();
k=path(s);
if (k==1)
{
printf("迷宫有路:\n");
print(s);
}
else
printf("迷宫没路\n\n");
}
31-27-2.rar_M?n
版权申诉
52 浏览量
2022-09-22
20:46:42
上传
评论
收藏 1KB RAR 举报
寒泊
- 粉丝: 75
- 资源: 1万+