迷宮問(wèn)題參考模板

1、迷宮問(wèn)題typedef int ElemType; /* 棧元素類型為整型 */typedef int Status;typedef int Boolean; #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0#includec3-1.h #includebo3-1.c/* c3-1.h 棧的順序存儲(chǔ)表示 */ #define STACK_INIT_SIZE 10 /* 存儲(chǔ)空間初始分配量 */ #define STACKINCREMENT 2 /* 存儲(chǔ)空間分配增量 */ typedef struct SqStack Ele

2、mType *base; /* 在棧構(gòu)造之前和銷毀之后，base的值為NULL */ ElemType *top; /* 棧頂指針 */ int stacksize; /* 當(dāng)前已分配的存儲(chǔ)空間，以元素為單位 */ SqStack; /* 順序棧 */* bo3-1.c 順序棧的基本操作（9個(gè)） */ Status InitStack(SqStack *S)1 / 18 /* 構(gòu)造一個(gè)空棧S */ (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType); if(!(*S).base) exit(-1); /* 存儲(chǔ)分配失敗

3、*/ (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; return OK; Status DestroyStack(SqStack *S) /* 銷毀棧S，S不再存在 */ free(*S).base); (*S).base=NULL; (*S).top=NULL; (*S).stacksize=0; return OK; Status ClearStack(SqStack *S) /* 把S置為空棧 */ (*S).top=(*S).base; return OK; Status StackEmpty(SqStack S) /* 若棧S

4、為空棧，則返回TRUE，否則返回FALSE */ if(S.top=S.base) return TRUE; else return FALSE; int StackLength(SqStack S) /* 返回S的元素個(gè)數(shù)，即棧的長(zhǎng)度 */ return S.top-S.base; Status GetTop(SqStack S,ElemType *e) /* 若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR */ if(S.topS.base) *e=*(S.top-1); return OK; else return ERROR; Status Push(SqStack

5、*S,SElemType e) /* 插入元素e為新的棧頂元素 */ if(*S).top-(*S).base=(*S).stacksize) /* 棧滿，追加存儲(chǔ)空間 */ (*S).base=(SElemType *)realloc(*S).base,(*S).stacksize+STACKINCREMENT)*sizeof(ElemType); if(!(*S).base) exit(-1); /* 存儲(chǔ)分配失敗 */ (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; *(*S).top)+=e; ret

6、urn OK; Status Pop(SqStack *S,SElemType *e) /* 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR */ if(*S).top=(*S).base) return ERROR; *e=*-(*S).top; return OK; Status StackTraverse(SqStack S,Status(*visit)(ElemType) /* 從棧底到棧頂依次對(duì)棧中每個(gè)元素調(diào)用函數(shù)visit()。 */ /* 一旦visit()失敗，則操作失敗 */ while(S.topS.base) visit(*S.base+);

7、printf(n); return OK; 一、非遞歸算法-利用棧求解迷宮問(wèn)題（只輸出一個(gè)解） */ typedef struct /* 迷宮坐標(biāo)位置類型 */ int x; /* 行值 */ int y; /* 列值 */ PosType; #define MAXLENGTH 25 /* 設(shè)迷宮的最大行列為25 */ typedef int MazeTypeMAXLENGTHMAXLENGTH; /* 迷宮數(shù)組行列 */ /* 全局變量 */ MazeType m; /* 迷宮數(shù)組 */ int curstep=1; /* 當(dāng)前足跡,初值為1 */ typedef struct /* 棧的元

8、素類型 */ int ord; /* 通道塊在路徑上的序號(hào) */ PosType seat; /* 通道塊在迷宮中的坐標(biāo)位置 */ int di; /* 從此通道塊走向下一通道塊的方向(03表示東北) */ ElemType; /* 定義墻元素值為0,可通過(guò)路徑為1,不能通過(guò)路徑為-1,通過(guò)路徑為足跡 */ Status Pass(PosType b) /* 當(dāng)迷宮m的b點(diǎn)的序號(hào)為1(可通過(guò)路徑)，return OK; 否則，return ERROR。 */ if(mb.xb.y=1) return OK; else return ERROR; void FootPrint(PosType a

9、) /* 使迷宮m的a點(diǎn)的序號(hào)變?yōu)樽阚E(curstep) */ ma.xa.y=curstep; PosType NextPos(PosType c,int di) /* 根據(jù)當(dāng)前位置及移動(dòng)方向，返回下一位置 */ PosType direc4=0,1,1,0,0,-1,-1,0; /* 行增量,列增量 */ /* 移動(dòng)方向,依次為東南西北 */ c.x+=direcdi.x; c.y+=direcdi.y; return c; void MarkPrint(PosType b) /* 使迷宮m的b點(diǎn)的序號(hào)變?yōu)?1(不能通過(guò)的路徑) */ mb.xb.y=-1; Status MazePath

10、(PosType start,PosType end) /* 若迷宮maze中存在從入口start到出口end的通道，則求得一條 */ /* 存放在棧中(從棧底到棧頂)，并返回TRUE；否則返回FALSE */ SqStack S; PosType curpos; ElemType e; InitStack(&S); curpos=start; do if(Pass(curpos) /* 當(dāng)前位置可以通過(guò)，即是未曾走到過(guò)的通道塊 */ FootPrint(curpos); /* 留下足跡 */ e.ord=curstep; e.seat.x=curpos.x; e.seat.y=curpos.

11、y; e.di=0; Push(&S,e); /* 入棧當(dāng)前位置及狀態(tài) */ curstep+; /* 足跡加1 */ if(curpos.x=end.x&curpos.y=end.y) /* 到達(dá)終點(diǎn)(出口) */ return TRUE; curpos=NextPos(curpos,e.di); else /* 當(dāng)前位置不能通過(guò) */ if(!StackEmpty(S) Pop(&S,&e); /* 退棧到前一位置 */ curstep-; while(e.di=3&!StackEmpty(S) /* 前一位置處于最后一個(gè)方向(北) */ MarkPrint(e.seat); /* 留下不

12、能通過(guò)的標(biāo)記(-1) */ Pop(&S,&e); /* 退回一步 */ curstep-; if(e.di3) /* 沒(méi)到最后一個(gè)方向(北) */ e.di+; /* 換下一個(gè)方向探索 */ Push(&S,e); curstep+; curpos=NextPos(e.seat,e.di); /* 設(shè)定當(dāng)前位置是該新方向上的相鄰塊 */ while(!StackEmpty(S); return FALSE; void Print(int x,int y) /* 輸出迷宮的解 */ int i,j; for(i=0;ix;i+) for(j=0;jy;j+) printf(%3d,mij);

13、printf(n); void main() PosType begin,end; int i,j,x,y,x1,y1; printf(請(qǐng)輸入迷宮的行數(shù),列數(shù)(包括外墻)：); scanf(%d,%d,&x,&y); for(i=0;ix;i+) /* 定義周邊值為0(同墻) */ m0i=0; /* 行周邊 */ mx-1i=0; for(j=1;jy-1;j+) mj0=0; /* 列周邊 */ mjy-1=0; for(i=1;ix-1;i+) for(j=1;jy-1;j+) mij=1; /* 定義通道初值為1 */ printf(請(qǐng)輸入迷宮內(nèi)墻單元數(shù)：); scanf(%d,&j)

14、; printf(請(qǐng)依次輸入迷宮內(nèi)墻每個(gè)單元的行數(shù),列數(shù)：n); for(i=1;i=j;i+) scanf(%d,%d,&x1,&y1); mx1y1=0; /* 定義墻的值為0 */ printf(迷宮結(jié)構(gòu)如下:n); Print(x,y); printf(請(qǐng)輸入起點(diǎn)的行數(shù),列數(shù)：); scanf(%d,%d,&begin.x,&begin.y); printf(請(qǐng)輸入終點(diǎn)的行數(shù),列數(shù)：); scanf(%d,%d,&end.x,&end.y); if(MazePath(begin,end) /* 求得一條通路 */ printf(此迷宮從入口到出口的一條路徑如下:n); Print(x,

15、y); /* 輸出此通路 */ else printf(此迷宮沒(méi)有從入口到出口的路徑n); 二、遞歸算法-用遞歸函數(shù)求解迷宮問(wèn)題(求出所有解) #include struct PosType /* 迷宮坐標(biāo)位置類型 */ int x; /* 行值 */ int y; /* 列值 */ ; #define MAXLENGTH 25 /* 設(shè)迷宮的最大行列為25 */ typedef int MazeTypeMAXLENGTHMAXLENGTH; /* 行列 */ /* 全局變量 */ struct PosType end; /* 迷宮終點(diǎn)位置 */ MazeType m; /* 迷宮數(shù)組 */

16、int x,y; /* 迷宮行數(shù)，列數(shù) */ /* 定義墻元素值為0,可通過(guò)路徑為-1,通過(guò)路徑為足跡 */ void Print(int x,int y) /* 輸出解 */ int i,j; for(i=0;ix;i+) for(j=0;jy;j+) printf(%3d,mij); printf(n); printf(n); void Try(struct PosType cur,int curstep) /* 由當(dāng)前位置cur、當(dāng)前步驟curstep試探下一點(diǎn) */ int i; struct PosType next; /* 下一個(gè)位置 */ struct PosType direc

17、4=0,1,1,0,0,-1,-1,0; /* 行增量,列增量 */ /* 移動(dòng)方向,依次為東南西北 */ for(i=0;i=3;i+) /* 依次試探東南西北四個(gè)方向 */ next.x=cur.x+direci.x; next.y=cur.y+direci.y; if(mnext.xnext.y=-1) /* 是通路 */ mnext.xnext.y=+curstep; if(next.x!=end.x|next.y!=end.y) /* 沒(méi)到終點(diǎn) */ Try(next,curstep); /* 試探下一點(diǎn)(遞歸調(diào)用) */ else Print(x,y); /* 輸出結(jié)果 */ mn

18、ext.xnext.y=-1; /* 恢復(fù)為通路，試探下一條路 */ curstep-; void main() struct PosType begin; int i,j,x1,y1; printf(請(qǐng)輸入迷宮的行數(shù),列數(shù)(包括外墻)：); scanf(%d,%d,&x,&y); for(i=0;ix;i+) /* 定義周邊值為0(同墻) */ m0i=0; /* 行周邊 */ mx-1i=0; for(j=1;jy-1;j+) mj0=0; /* 列周邊 */ mjy-1=0; for(i=1;ix-1;i+) for(j=1;jy-1;j+) mij=-1; /* 定義通道初值為-1 */ printf(請(qǐng)輸入迷宮內(nèi)墻單元數(shù)