#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空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
