maze.txt

这个是BRISTOL大学 大二的作业. 当时得了90多分所以如果有国外留学生朋友可以看看.

#include<stdio.h>
#include<stdlib.h>
#define SIS 100/*运行栈一次分配的空间*/
#define N 10/*迷宫的最大坐标，根据迷宫大小修改*/
struct sit/*数据结构定义迷宫坐标*/
{
int seatx;
int seaty;
};
struct finds
{
int ord;/*路径标号*/
struct sit *seat;
int di;/*下一步试探的方向，上下左右用1，2，3，4来表示*/
};
struct stack/*定义运行栈*/
{
struct finds *base;
struct finds *top;
int size;
};
void initstack(struct stack *s)/*构造运行栈*/
{
struct finds *link,*end;
s->base=s->top=link=(struct finds *)malloc(SIS*sizeof(struct finds));
end=link+SIS-1;
for(;link<=end;link++)
link->seat=(struct sit *)malloc(sizeof(struct sit));
s->size=SIS;
}
void push(struct stack *s,struct finds *find)/*把*find压入栈s，栈定指针加1*/
{
struct finds *link,*end;
if(s->top-s->base>=s->size)
{
s->base=(struct finds *)realloc(s->base,(s->size+SIS)*sizeof(struct finds));
link=s->base+s->size;
s->top=s->size+s->base;
s->size+=SIS;
end=s->base+s->size;
for(;link<=end;link++)
link->seat=(struct sit *)malloc(sizeof(struct sit));

}
s->top->ord=find->ord;
s->top->seat->seatx=find->seat->seatx;
s->top->seat->seaty=find->seat->seaty;
s->top->di=find->di;
s->top++;
}
void pop(struct stack *s,struct finds *find)/*栈顶元素*find出栈*/
{
s->top--;
find->ord=s->top->ord;
find->seat->seatx=s->top->seat->seatx;
find->seat->seaty=s->top->seat->seaty;
find->di=s->top->di;
}
void footprint(int a[N][N],struct sit *seat)/*走过的路经留下足迹，也就是将坐标值为非零*/
{
int i,j;
i=seat->seatx;
j=seat->seaty;
a[i][j]=-1;
}
void nextpos(struct sit *find,struct sit *seat,int di)/*规定下一步试探的方向*/
{
int i,j;
switch(di)
{case 1:i=seat->seatx;j=seat->seaty+1;break;
case 2:i=seat->seatx+1;j=seat->seaty;break;
case 3:i=seat->seatx;j=seat->seaty-1;break;
case 4:i=seat->seatx-1;j=seat->seaty;break;
}
find->seatx=i;
find->seaty=j;
}
int pass(struct sit *curpos,int a[N][N])/*判断改足迹是否走过，走过为1否则为0，进行下一步试探*/
{
int i,j;
i=curpos->seatx;
j=curpos->seaty;
if(a[i][j]==0)return 1;
else return 0;
}

print(struct stack *s)/*输出结果，输出结果不太好看，但这不是程序的关键部分，你可以自己修改输出方法*/
{ do
{
printf("(%d,%d)",s->base->seat->seatx,s->base->seat->seaty);
s->base++;
}while(s->top!=s->base);
}
void main()
{
struct stack *s;
struct finds *find,*e;
struct sit *start,*end,*curpos;
int curstep=1,a[N][N],i,j,n,m,pa;
char c[N][N];
s=(struct stack *)malloc(sizeof(struct stack));
find=(struct finds *)malloc(sizeof(struct finds));
e=(struct finds *)malloc(sizeof(struct finds));
start=(struct sit *)malloc(sizeof(struct sit));
end=(struct sit *)malloc(sizeof(struct sit));
curpos=(struct sit *)malloc(sizeof(struct sit));
initstack(s);
puts("在使用前请仔细阅读使用说明");
while(1)
{
printf("请输入迷宫的长和宽（n，m）");
pa=scanf("%d,%d",&n,&m);
if(pa!=2||n>81||m>81||n<=0||m<=0)puts("输入数据错误,请重新输入");
else break;
}

printf("请输入你的迷宫（0代表路径,连续输入）\n");
for(i=0;i<n;i++)
scanf("%s",c[i]);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
a[i][j]=c[i][j]-48;
while(1)
{
printf("进入迷宫的位置（n，m）");
scanf("%d,%d",&curpos->seatx,&curpos->seaty);
if(curpos->seatx>81||curpos->seaty>81||curpos->seatx<=0||curpos->seaty<=0||curpos->seatx>=n||curpos->seatx>=m||curpos->seaty>=m||curpos->seaty>=n)puts("输入数据错误,请重新输入");
else break;

}
while(1)
{
printf("走出迷宫的位置（n，m）");
scanf("%d,%d",&end->seatx,&end->seaty);
if(end->seatx>81||end->seaty>81||end->seatx<=0||end->seaty<=0||end->seatx>=n||end->seatx>=m||end->seaty>=n||end->seaty>=m)puts("输入数据错误,请重新输入");
else break;
}

do
{
if(pass(curpos,a))
{footprint(a,curpos);
e->ord=curstep;
e->seat=curpos;
e->di=1;
push(s,e);
if(curpos->seatx==end->seatx&&curpos->seaty==end->seaty)break;
nextpos(curpos,e->seat,1);
curstep++;
} 
else {
if(e->di<4){pop(s,e);e->di++,push(s,e);nextpos(curpos,e->seat,e->di);}
else if(e->di==4)
{
pop(s,e);pop(s,e);push(s,e);e->di++;
if(e->di>4)pop(s,e);
nextpos(curpos,e->seat,e->di);
}
}

}while(1);
puts("输出路径为");
print(s);
puts("\n");

}