#include <stdio.h>
#include<time.h>
#include<stdlib.h>
#include<conio.h>
typedef struct {
unsigned ord,x,y;/*通道块在路径上的序号和在迷宫中的坐标位置*/
short di; /* 从此通道块走向下一通道块的“方向” */
} ElemType;
typedef struct Node { /* 定义单链表 */
ElemType data;
struct Node* next;
} Node,*LinkList;
typedef struct { /* 定义链栈结构 */
LinkList top; /* 栈顶指针 */
unsigned length; /* 栈中元素个数 */
} LStack;
void DestroyStack( LStack *S ) /* 销毁栈 */
{ LinkList q;
while ( S->top ) {
q = S->top;
S->top = S->top->next; /* 修改栈顶指针 */
free( q );/* 释放被删除的结点空间 */
}
S->length = 0;
}
void InitStack( LStack *S ) /* 构造空栈 */
{
S->top = NULL; /* 栈顶指针初值为空 */
S->length = 0; /* 空栈中元素个数为 0 */
}
int Pop( LStack *S,ElemType *e )
{ /* 若栈不空，则删除 S 的栈顶元素，用 e 返回栈顶元素的值。*/
LinkList q;
if(!S->top ) {
return 0;
}
*e = S->top->data; /* 返回栈顶元素 */
q = S->top;
S->top = S->top->next; /* 修改栈顶指针 */
--S->length;/* 栈的长度减1 */
free( q );/* 释放被删除的结点空间 */
return 1;
}
int Push( LStack *S,ElemType e )
{ /* 在栈顶之上插入元素 e 为新的栈顶元素 */
LinkList p = (Node*)malloc( sizeof *p ); /* 建新的结点 */
if (!p ) {
return 0;/* 存储分配失败 */
}
p->data = e;
p->next = S->top; /* 链接到原来的栈顶 */
S->top = p; /* 移动栈顶指针 */
++S->length; /* 栈的长度增1 */
return 1;
}
void NextPos(unsigned *x,unsigned *y,short di) /* 定位下一个位置 */
{
switch (di) {
case 1:++(*x);break;
case 2:++(*y);break;
case 3:--(*x);break;
case 4:--(*y);break;
default:
break;
}
} /* 定位下一个位置 */
int main( void )
{
LStack S,T;
unsigned x,y,curstep,i=0;/* 迷宫坐标，探索步数 */
ElemType e;
InitStack(&S);
InitStack(&T);
printf("迷宫图形，1代表墙壁，0代表通路：\n");
/*int way;
printf("欢迎来到迷宫");
printf("系统随机生成迷宫请按1，自定义请按2");
scanf("%d",&way);
int maze[100][100];
if(way==1)
{
int size,k;
srand((unsigned)time(NULL));
printf("请输入迷宫的长和宽\n ") ;
scanf("%d",&size);
for(y=0;y<size;y++)//迷宫建立
{maze[0][y]=1;
maze[size-1][y]=1;}
for(x=0;x<size-1;x++)
{maze[x][0]=1;
maze[x][size-1]=1;}
for(x=1;x<size-1;x++)
{
for(y=1;y<size-1;y++)
{
k=rand()%2;
if(k)
maze[x][y]=0;
else
maze[x][y]=1;
}
}
for(x=0;x<size;x++)
{ for(y=0;y<size;y++)
printf("%5d",maze[x][y]);
printf("\n");}
}
if(way==2)
{
int maze[12][12]=
{1,1,1,1,1,1,1,1,1,1,1,1,
1,0,0,0,1,0,0,0,0,1,1,1,
1,1,1,0,1,1,0,1,1,1,1,1,
1,0,1,0,0,0,1,1,1,0,1,1,
1,1,1,1,1,0,1,1,1,1,1,1,
1,1,0,1,1,0,0,0,0,1,0,1,
1,1,1,0,1,1,1,1,0,1,1,1,
1,1,1,1,0,1,1,0,0,0,0,1,
1,1,0,1,1,1,1,0,0,0,0,1,
1,0,1,0,1,0,1,0,0,0,0,1,
1,1,1,1,0,0,0,1,0,1,0,1,
1,1,1,1,1,1,1,1,1,1,1,1
};
for(x=0;x<12;x++)
{ for(y=0;y<12;y++)
printf("%5d",maze[x][y]);
printf("\n");
}
}*/
int maze[12][12]=
{1,1,1,1,1,1,1,1,1,1,1,1,
1,0,0,0,1,0,0,0,0,1,1,1,
1,0,1,0,1,1,0,1,1,1,1,1,
1,0,1,0,0,0,1,1,1,0,1,1,
1,0,1,1,1,0,1,1,1,1,1,1,
1,1,0,1,1,0,0,0,0,1,0,1,
1,1,1,0,1,1,1,1,0,1,1,1,
1,1,1,1,0,1,1,0,0,0,0,1,
1,1,0,1,1,1,1,0,0,0,0,1,
1,0,1,0,1,0,1,0,0,0,0,1,
1,1,1,1,0,0,0,1,0,1,0,1,
1,1,1,1,1,1,1,1,1,1,1,1
};
for ( x = 0;x < 12;x++) {
for ( y = 0;y < 12;y++ )
{
printf("%5d",maze[x][y]);
}
printf("\n");
}
x = 1; /*迷宫起点*/
y = 1;
curstep = 1; /* 探索第一步 */
do { /* 进入迷宫 */
if ( maze[y][x] == 0) { /* 如果当前位置可以通过 */
maze[y][x] = 8;/* 留下足迹 */
e.x = x;
e.y = y;
e.di = 1;
e.ord = curstep;
if (!Push(&S,e) ) { /* 加入路径，即压栈 */
fprintf( stderr,"内存不足。\n" );
}
if ( x == 10 && y == 10 ) { /* 到达终点 */
break;
}
NextPos(&x, &y, 1); /* 下一位置是当前位置的东邻 */
curstep++;
}
else { /* 如果当前位置不能通过 */
if (S.length!=0) {
Pop(&S,&e);
while (e.di == 4 && S.length!=0)
{ maze[y][x]=6; /* 留下不能通过足迹 */
Pop(&S, &e); /* 退回一步，即出栈 */
}
if (e.di < 4) {
e.di++;
if (!Push(&S,e) ) { /* 加入路径，即压栈 */
fprintf( stderr,"内存不足。\n" );
}
x = e.x; /* 重置坐标 */
y = e.y;
NextPos(&x,&y,e.di); /* 寻找下一位置 */
}
}
}
} while (S.length!=0);
printf("走出迷宫路线，8代表走过的路，4代表试探过的路径\n");
for ( x = 0;x < 12;x++ ) {
for ( y = 0;y < 12;y++ ) {
printf("%5d",maze[x][y]);
if(maze[x][y]==8)
i++;
}
printf("\n");
}
for(x=0;x<i;x++)
{ Pop(&S,&e);
Push(&T,e);
}
printf("出迷宫顺序，（X坐标，Y坐标，前进方向）：\n");
while(T.length!=0)
{ printf("(%d，%d，%d)\t",T.top->data.x,T.top->data.y,T.top->data.di);
Pop(&T,&e);
}
DestroyStack(&S);
return 0;
}
|
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
淘帖
顶
踩
