迷宮實(shí)驗(yàn)報(bào)告

1、.1、 實(shí)驗(yàn)內(nèi)容3、 迷宮問(wèn)題。假設(shè)迷宮由m行n列構(gòu)成，有一個(gè)出口和一個(gè)入口，入口坐標(biāo)為（1,1），出口坐標(biāo)為（m,n），試設(shè)計(jì)并驗(yàn)證以下算法：找出一條從入口通往出口的路徑，或報(bào)告一個(gè)“無(wú)法通過(guò)”的信息。（1）用C語(yǔ)言實(shí)現(xiàn)順序存儲(chǔ)隊(duì)列上的基本操作，然后利用該隊(duì)列的基本操作找出迷宮的一條最短路徑。（2）設(shè)計(jì)一個(gè)二維數(shù)組MAZEm+2n+2表示迷宮，數(shù)組元素為0表示該位置可以通過(guò)，數(shù)組元素為1表示該位置不可以通行。MAZE11、MAZEmn分別為迷宮的入口和出口。（3）輸入迷宮的大小m行和n列，動(dòng)態(tài)生成二維數(shù)組；由隨機(jī)數(shù)產(chǎn)生0或1，建立迷宮，注意m*n的迷宮需要進(jìn)行擴(kuò)展，擴(kuò)展部分的元素設(shè)置為1，相

2、當(dāng)于在迷宮周?chē)忌弦蝗Σ粶?zhǔn)通過(guò)的墻。（4）要求輸出模擬迷宮的二維數(shù)組；若存在最短路徑，則有出口回溯到入口（出隊(duì)列并利用棧實(shí)現(xiàn)），再打印從入口到出口的這條路徑，例如（1,1），.，（i,j），.，（m,n）；若沒(méi)有路徑，則打印“No path”。（5）迷宮的任一位置（i,j）上均有八個(gè)可移動(dòng)的方向，用二維數(shù)組Direction存放八個(gè)方向的位置偏移量。Direction82=0,1，1,1，0，-1，-1，-1，1,-1，1,0，-1,0，-1,1；（6） 為避免出現(xiàn)原地踏步的情況需要標(biāo)志已經(jīng)通過(guò)的位置，采用一個(gè)標(biāo)志數(shù)組MARKm+2n+2，初值均為0，在尋找路徑的過(guò)程中，若通過(guò)了位置（i，j）

3、，則將MARKij置為1。（7） 為了記錄查找過(guò)程中到達(dá)位置（i，j）及首次到達(dá)（i,j）的前一位置（i_pre,j_pre），需要記住前一位置（i_pre,j_pre）在隊(duì)列中的序號(hào)pre，即隊(duì)列中數(shù)據(jù)元素應(yīng)該是一個(gè)三元組（i,j,pre）。（8） 搜索過(guò)程簡(jiǎn)單下：將入口MAZE11作為第一個(gè)出發(fā)點(diǎn)，依次在八個(gè)方向上搜索可通行的位置，將可通行位置（i,j,pre）入隊(duì)，形成第一層新的出發(fā)點(diǎn)，然后依次出隊(duì)，即對(duì)第一層中各個(gè)位置分別搜索它所在八個(gè)方向上的可通行位置，形成第二層新的出發(fā)點(diǎn)，.，如此進(jìn)行下去，直至達(dá)到出口MAZEmn或者迷宮所有位置都搜索完畢為止。2、 實(shí)驗(yàn)過(guò)程及結(jié)果1、 需求分析1

4、、用棧的基本操作完成迷宮問(wèn)題的求解，其中棧的基本操作作為一個(gè)獨(dú)立的模塊存在。2、以二維數(shù)組Mm+2n+2表示迷宮，Mij 表示迷宮中相應(yīng)（i,j）位置的通行狀態(tài)（0:表示可以通行，1：表示有墻，不可通行），完成迷宮的抽象數(shù)據(jù)類(lèi)型，包括出口、入口位置等。3、用戶從屏幕上輸入迷宮，從鍵盤(pán)輸入迷宮的大小，即迷宮的長(zhǎng)和寬(由于控制臺(tái)大小限制，輸入的長(zhǎng)寬需在50以下)，完成對(duì)應(yīng)迷宮的初始化。根據(jù)鍵盤(pán)輸入的迷宮規(guī)格隨機(jī)生成大小相同的迷宮，產(chǎn)生方塊的地方為墻，無(wú)方塊的地方可通過(guò)，如下例所示：如下所示：4、程序完成對(duì)迷宮路徑的搜索，為了更好地顯示出求解結(jié)果，如果存在路徑，則以長(zhǎng)方形形式將迷宮打印出來(lái)，而不是只

5、按步輸出坐標(biāo)，也便于檢查路徑的正確性，用特定符號(hào)標(biāo)出迷宮的物理狀態(tài)，其中字符“#”表示出口和入口，“”標(biāo)記出可行的路徑；如果程序完成搜索后沒(méi)有找到通路，則提示用戶“No Path!”。如圖所示：5、 程序執(zhí)行的命令： 創(chuàng)建初始化迷宮； 搜索迷宮； 輸出搜索到的最短路徑。2、 概要設(shè)計(jì)（按照題目要求應(yīng)該用隊(duì)列實(shí)現(xiàn)路徑的存儲(chǔ)，但操作過(guò)程中遇到很多困難未能解決，故選擇棧的操作來(lái)實(shí)現(xiàn)路徑的存儲(chǔ)）1、迷宮的抽象數(shù)據(jù)類(lèi)型定義：ADT Maze數(shù)據(jù)對(duì)象：D：=aij,Start,end|-20=aij20,Start,end(i,j)|0im+2,0jn+2,m,n0 數(shù)據(jù)關(guān)系：R=length，width

6、 length=|ai-1,aijD i=1,m+2,j=1,n+2 width=|aijaij-1D基本操作: SetMaze(&M) 初始條件：M已經(jīng)定義，M的下屬單元二維數(shù)組M.Mazerow+2d+2已存在，M.start,M.end也已作為下屬存儲(chǔ)單元存在 操作結(jié)果：構(gòu)成數(shù)據(jù)迷宮，用數(shù)值標(biāo)識(shí)迷宮的物理狀態(tài)，以0表示通路，以1表示障礙，由終端讀取迷宮空間大小，各點(diǎn)處的具體物理狀態(tài)及Start和End點(diǎn)位置，完成迷宮構(gòu)建 Pass(M, CurPos) 初始條件：已知目前迷宮狀態(tài)及當(dāng)前位置 操作結(jié)果：完成相應(yīng)的搜索任務(wù)，如果可行，則返回1 NextPos(CurPos, directio

7、nr) 操作結(jié)果：返回CurPOS位置在方向direction上的下一位置 SameSeat(Path,row,col) 操作結(jié)果：若（row，col）位置是路徑Path中的一個(gè)點(diǎn)，則返回TRUE PrintMaze(M) 初始條件：迷宮M已存在 操作結(jié)果：輸出字符標(biāo)示的迷宮 MazePath(M,&Path) 初始條件：迷宮M已存在 操作結(jié)果：搜索迷宮，用path返回搜索所得路徑。如不存在，返回0 PrintPath(M,Path) 初始條件：迷宮M已存在 操作結(jié)果：迷宮M存在可行路徑則將迷宮M及相應(yīng)最短路徑一起打印輸出ADT MAZE； 本程序模塊結(jié)構(gòu) 主函數(shù)模塊void main()初始

8、化迷宮和棧；創(chuàng)建迷宮；輸出迷宮；搜索路徑；輸出路徑； 棧模塊實(shí)現(xiàn)棧抽象數(shù)據(jù)類(lèi)型； 迷宮模塊實(shí)現(xiàn)迷宮抽象數(shù)據(jù)類(lèi)型；各模塊之間的調(diào)用關(guān)系如下：主程序模塊 迷宮模塊 棧模塊3、 詳細(xì)設(shè)計(jì)1、基本數(shù)據(jù)類(lèi)型操作 棧模塊 typedef structint order;Position seat;int direction;SElemType;/步數(shù)、方向及位置/棧定義 typedef struct lnodeSElemType *base;SElemType *top;/設(shè)兩指針便于判斷棧是否為空int stacksize;/棧當(dāng)前可使用的最大容量SqStack; 參數(shù)設(shè)置：#define STACK_

9、INIT_SIZE 100#define STACKINCRENT 10/-基本操作的算法描述-Status InitStack(SqStack &s) / 構(gòu)造一個(gè)空棧S.base=(SelemType )malloc(STACK_INIT_SIZE*SizeOf(SelemType);if(!S.base)exit(OVERLOW); / 存儲(chǔ)分配失敗S.top=S.base;S.stacksize=STACK_INIT_SIZE;return ok;Status StackEmpty(Sqstack &S) / 若S為空返回TRUE，否則返回FALSEreturn S.base=S.to

10、p;Status GetTop(SqStack &S,Selemtype &e) / 棧不空，用e返回s的棧頂元素及OK，否則返回ERRORif(S.top=S.base)return ERROR;e=*(S.top-1);return ok; Status Push(Sqstack &S,SelemType &e) / 插入元素e為新的棧頂元素if(S.top-S.base=S.stacksize)/ 棧滿追加存儲(chǔ)空間S.base=(SelemType)realloc(S.base,(S.stacksize+STACKICREMENT)Sizeof(Selemtype);if(!S.base

11、) exit(OVERFLOW) / 存儲(chǔ)分配失敗S.top=S.base+S.stacksize; / 確定新的棧頂指針S.stacksize+=STACKINCREMENT;/ 已分配空間增加 *S.top+=*e;return ok;Status Pop(Sqstack &s,SelemType &e)/ 若棧不變，則刪除棧頂元素，用e返回其值及ok,否則falseif(S.top=o=S.base)return ERROR;*e=*-S.top; / 頂指針減小，用e返回其數(shù)據(jù)return ok; 迷宮模塊： 迷宮的數(shù)據(jù)類(lèi)型 #define MAXLENGTH 50/ 迷宮的最大長(zhǎng)度#

12、define MAXWIDTH 50/ 屏幕寬度，迷宮的最大寬度/元素類(lèi)型typedef int Status;typedef structint row;int col;Position;/位置坐標(biāo)/迷宮定義typedef int ElemType;typedef struct MAZEElemType MazeMAXLENGTHMAXWIDTH;/ 迷宮的物理狀態(tài)描述int length,width;/ 迷宮的大小Position start,end;/ 開(kāi)始與結(jié)束位置與棧的單元類(lèi)型相同MAZE;/ “迷宮”型數(shù)據(jù)迷宮模塊中的基本操作Status semaze(MAZE &M)Printf

13、(“Please input the length and width of the MAZE”);sanf(“rlength,width”);for(k=0;kMaze0k=1;for(j=0;jMazej0=1;for(j=0;jMazejwidth+1=1;for(k=0;kMazelength+1k=1;/設(shè)置迷宮圍墻for(j=1;j=length;j+)for(k=1;kMazejk=rand()%2;/隨機(jī)生成迷宮 M-length=length;M-width=width;M-start.row=1;M-start.col=1;M-end.row=M-length;M-end.

14、col=M-width;M-MazeM-start.rowM-start.col=M-MazeM-end.rowM-end.col=0;/入口和出口設(shè)置*/void PrintMaze(MAZE M) / 打印出迷宮，包括邊界printf(迷宮入口:1,1-用#表示n);printf(迷宮出口:%d,%d-用#表示n,M.length,M.width);for(row=0;rowM.length+2;row+)for(col=0;colM.width+2;col+)if(row=1&col=1)|(row=M.length&col=M.width)printf(# );/入口和出口用#表示el

15、seprintf(%c ,M.Mazerowcol);printf(n);/ 用字符型打印輸出（i,j）狀態(tài)Status Pass( MAZE M,Position CurPos) / 判斷迷宮中當(dāng)前位置CurPos上能否通過(guò)/ 如果通過(guò)返回1 if (M.MazeCurPos.rowCurPos.col=0) return 1; / 如果當(dāng)前位置是可以通過(guò)，返回1 else return 0; / 其它情況返回0Position NextPos(Position CurPos, int direction) /返回當(dāng)前位置在direction方向上的下一位置ReturnPos.row=Cur

16、Pos.row+Directiondirection-10;ReturnPos.col=CurPos.col+Directiondirection-11; return ReturnPos;Status SameSeat(SqStack Path,int row,int col)/位置（row，col）在路徑中時(shí)返回TRUEwhile(pPath.top)if(Path.basenum.seat.row=row&Path.basenum.seat.col=col)/路徑某一步所在的位置return TRUE;num+;p+;return FALSE;Status MazePath(MAZE M

17、,SqStack *S) / 若迷宮maze中從入口 start到出口 end的通道，則求得一條存放在棧中/ （從棧底到棧頂），并返回SUCCESS；否則返回FAILcurpos=M.start; / 設(shè)定當(dāng)前位置為入口位置curstep=1; / 探索第一步/第一次查找路徑，設(shè)置5個(gè)方向(不遠(yuǎn)離!終點(diǎn)的五個(gè)方向)，若找到則返回SUCCESSdo if(Pass(M,curpos) / 當(dāng)前位置可通過(guò)，即是未曾走到過(guò)的通道塊 M.Mazecurpos.rowcurpos.col= ; / 留下足跡 e.direction=1; e.order=curstep; e.seat=curpos; P

18、ush(S,&e); / 加入路徑 if(curpos.row=M.end.row&curpos.col=M.end.col) / 到達(dá)終點(diǎn)（出口） return SUCCESS; curpos=NextPos(curpos,1); / 下一位置在當(dāng)前位置的右下方 curstep+; / 探索下一步 else / 當(dāng)前位置不能通過(guò) if(!StackEmpty(S) Pop(S,&e); while(e.direction=5&!StackEmpty(S) M.Mazecurpos.rowcurpos.col= ;/標(biāo)記不能通過(guò) Pop(S,&e); / 留下不能通過(guò)的標(biāo)記，并退回一步 / w

19、hile if(e.direction5) e.direction+; GetTop(S,&te); if(e.direction=5&te.direction=2) Pop(S,&e); e.direction+; Push(S,&e); / 換下一個(gè)方向探索 curpos=NextPos(e.seat,e.direction); / 當(dāng)前位置設(shè)為新方向的相鄰塊 / if / if / elsewhile(!StackEmpty(S);curpos=M.start; / 設(shè)定當(dāng)前位置為入口位置curstep=1; / 探索第一步/如果第一次查找無(wú)結(jié)果則再進(jìn)行一次八個(gè)方向的查找，檢查是否存在第

20、一次查找不到的特殊情況do if(Pass(M,curpos) / 當(dāng)前位置可通過(guò)，即是未曾走到過(guò)的通道塊 M.Mazecurpos.rowcurpos.col= ; / 留下足跡 e.direction=1; e.order=curstep; e.seat=curpos; Push(S,&e); / 加入路徑 if(curpos.row=M.end.row&curpos.col=M.end.col) / 到達(dá)終點(diǎn)（出口） /PrintPath(maze,S);/輸出路徑 return SUCCESS; curpos=NextPos(curpos,1); / 下一位置是當(dāng)前位置的東鄰 curs

21、tep+; / 探索下一步 else / 當(dāng)前位置不能通過(guò) if(!StackEmpty(S) Pop(S,&e); while(e.direction=8&!StackEmpty(S) M.Mazecurpos.rowcurpos.col= ;/標(biāo)記不能通過(guò) Pop(S,&e); / 留下不能通過(guò)的標(biāo)記，并退回一步 / while if(e.direction8) e.direction+; GetTop(S,&te); if(e.direction=4&te.direction=2) Pop(S,&e); e.direction+; Push(S,&e); / 換下一個(gè)方向探索 curpo

22、s=NextPos(e.seat,e.direction); / 當(dāng)前位置設(shè)為新方向的相鄰塊 / if / if / elsewhile(!StackEmpty(S);return FAIL; / MazePathvoid PrintPath(MAZE M, SqStack Path)/ 將迷宮及路徑一起打印if(StackEmpty(&Path)printf(No Path!n);/路徑棧為空，則提示無(wú)路徑exit(OVERFLOW);printf(nThe Path:n);for(row=0;rowM.length+2;row+)for(col=0;col );num+;p+;elsepr

23、intf(%c ,M.Mazerowcol);printf(n); 主函數(shù)算法：void main()MAZE M;SqStack path;InitStack(&path);SetMaze(&M);PrintMaze(M);MazePath(M,&path);PrintPath(M,path); 函數(shù)的調(diào)用關(guān)系反映了本演示程序的層次結(jié)構(gòu)迷宮處理工作棧設(shè)置mainInitStack MazePath PrintPath PrintMaze Pass SetMaze SameSeat NextPos Push GetTop Pop StackEmpty 4、 調(diào)試分析1、開(kāi)始沒(méi)有將Mnm.sta

24、rt.end設(shè)置為MAZE 型數(shù)據(jù)的下屬單元，使得各個(gè)迷宮操作的函數(shù)參數(shù)十分散雜，調(diào)試時(shí)各參數(shù)關(guān)系不易把握。2、另行設(shè)置PrintPath函數(shù)，使得終端輸出更加友好，并巧妙地將迷宮以特殊、明朗的字符輸出，效果更好。3、開(kāi)始出棧入棧的條件沒(méi)有控制好，導(dǎo)致輸出時(shí)不是完整路徑，甚至出錯(cuò)。4、選擇方向時(shí)有一定策略，開(kāi)始選擇時(shí)按照順時(shí)針依次讀取方向，發(fā)現(xiàn)太耗時(shí)且效果不好，容易出現(xiàn)不必要的彎折走法，后來(lái)通過(guò)控制方向順序，即第一方向?yàn)闁|南方，然后再東方、南方.，選取越靠近出口的方向?yàn)閮?yōu)先方向，因?yàn)檫@樣的話搜索路徑時(shí)自然會(huì)本著路徑最短的原則向出口處行進(jìn)，那么找到的路徑自然是最短路徑（之一）。5、由于八個(gè)方向的

25、特殊性，根據(jù)方向的順序，搜索路徑時(shí)仍會(huì)出現(xiàn)多走的情況，比如先往東再往西南，其實(shí)是可以直接往南的，因此為了避免這種情況，在入棧時(shí)還要先進(jìn)行這種情況的判斷，如是這種情況則出棧將前一位置方向改變?cè)偃霔！?、為了便于找到最短路徑，起初只使用了靠近出口處的五個(gè)方向，但是發(fā)現(xiàn)有特殊情況存在時(shí)由于不能想遠(yuǎn)離出口的方向行進(jìn)而找不到路徑，因此在搜索路徑時(shí)進(jìn)行了兩次搜索，第一次使用五個(gè)靠進(jìn)出口的方向搜索，找到路徑時(shí)則返回SUCCESS，若未搜索到則再進(jìn)行一次八個(gè)方向的搜索，即為了防止漏掉特殊情況，找到時(shí)則返回SUCCESS，由于第一搜索無(wú)結(jié)果若第二次搜索到路徑也只能是特殊情況，故也應(yīng)該是最短路徑（之一）。7、最大

26、的問(wèn)題是并沒(méi)有按照題目要求來(lái)做，因?yàn)轭}目中要求用隊(duì)列來(lái)存儲(chǔ)路徑，經(jīng)過(guò)實(shí)驗(yàn)發(fā)現(xiàn)有很多問(wèn)題難以解決，故選擇了只用棧的方法來(lái)實(shí)現(xiàn)。5、 用戶說(shuō)明 本程序的運(yùn)行環(huán)境為windows 7（64位）操作系統(tǒng)，執(zhí)行文件為數(shù)據(jù)結(jié)構(gòu)迷宮.exe； 進(jìn)入演示程序后，即顯示對(duì)話形式的提示操作過(guò)程， 1、提出輸入迷宮的大小2、按enter鍵輸出隨機(jī)生成的迷宮3、按enter鍵開(kāi)始搜索路徑搜索結(jié)果：The Path：輸出迷宮及路徑或者輸出No Path! 提示輸入迷宮大小后，用戶輸入所要處理迷宮的長(zhǎng)row，寬col； 提示輸入迷宮后，用戶將迷宮輸入，0代表可行，1代表障礙； 按任意鍵開(kāi)始后，程序自動(dòng)進(jìn)行對(duì)所建迷宮的搜索

27、，并將搜索結(jié)果； 按任意鍵退出程序。6、 測(cè)試結(jié)果1、 無(wú)路徑：2、 找到最短路徑：7、 附錄（源代碼及注釋）#include time.h#include stdio.h#include stdlib.h#include conio.h#define NULL 0#define TRUE 1#define FALSE 0#define SUCCESS 1#define FAIL 0#define OK 1#define ERROR 0#define OVERFLOW -1#define INFEASIBLE -2#define MAXLENGTH 50#define MAXWIDTH 50#

28、define STACK_INIT_SIZE 100#define STACKINCRENT 10/元素類(lèi)型typedef int Status;typedef structint row;int col;Position;/位置坐標(biāo)typedef structint order;Position seat;int direction;SElemType;/步數(shù)、方向及位置/棧定義typedef struct lnodeSElemType *base;SElemType *top;/設(shè)兩指針便于判斷棧是否為空int stacksize;/棧當(dāng)前可使用的最大容量SqStack;/迷宮定義type

29、def int ElemType;typedef struct MAZEElemType MazeMAXLENGTHMAXWIDTH;int length,width;Position start,end;MAZE;/迷宮大小及出入口位置/棧操作函數(shù)聲明Status InitStack(SqStack *S);/初始化Status StackEmpty(SqStack *S);/判空Status GetTop(SqStack *s,SElemType *e);/取棧頂元素Status Push(SqStack *S,SElemType *e);/入棧Status Pop(SqStack *s,

30、SElemType *e);/出棧/迷宮操作函數(shù)說(shuō)明void SetMaze(MAZE *M);/*設(shè)置迷宮，隨機(jī)生成*/void PrintMaze(MAZE M);/*輸出迷宮*/Status Pass(MAZE M, Position CurPos);/判斷當(dāng)前位置是否可通Position NextPos(Position CurPos, int directionr);/下一位置Status SameSeat(SqStack Path,int row,int col);/找到迷宮中可行路徑的各個(gè)位置Status MazePath(MAZE M,SqStack *Path);/搜索迷宮路

31、徑void PrintPath(MAZE M, SqStack Path);/若迷宮M存在可行路徑則將該路徑在迷宮中輸出/主函數(shù)void main()MAZE M;SqStack path;InitStack(&path);SetMaze(&M);PrintMaze(M);MazePath(M,&path);PrintPath(M,path);/迷宮操作void SetMaze(MAZE *M)int length,width,j,k;printf(Please input the length and width of the MAZE:nlength (0length=50):);scan

32、f(%d,&length);printf(width (0width=50):);scanf(%d,&width);srand(unsigned)time(NULL);for(k=0;kMaze0k=1;for(j=0;jMazej0=1;for(j=0;jMazejwidth+1=1;for(k=0;kMazelength+1k=1;/設(shè)置迷宮圍墻for(j=1;j=length;j+)for(k=1;kMazejk=rand()%2;/隨機(jī)生成迷宮M-length=length;M-width=width;M-start.row=1;M-start.col=1;M-end.row=M-le

33、ngth;M-end.col=M-width;M-MazeM-start.rowM-start.col=M-MazeM-end.rowM-end.col=0;/入口和出口設(shè)置*/void PrintMaze(MAZE M)int row,col;printf(迷宮入口:1,1-用#表示n);printf(迷宮出口:%d,%d-用#表示n,M.length,M.width);for(row=0;rowM.length+2;row+)for(col=0;colM.width+2;col+)if(row=1&col=1)|(row=M.length&col=M.width)printf(# );/入

34、口和出口用#表示elseprintf(%c ,M.Mazerowcol);printf(n);Status Pass( MAZE M,Position CurPos) if (M.MazeCurPos.rowCurPos.col=0) return 1; / 如果當(dāng)前位置是可以通過(guò)，返回1 else return 0; / 其它情況返回0Position NextPos(Position CurPos, int direction) Position ReturnPos;int Direction82=1,1,0,1,1,0,-1,1,1,-1,0,-1,-1,0,-1,-1;/按一定次序依次

35、設(shè)置八個(gè)方向ReturnPos.row=CurPos.row+Directiondirection-10;ReturnPos.col=CurPos.col+Directiondirection-11; return ReturnPos;Status SameSeat(SqStack Path,int row,int col)SElemType *p=Path.base;int num=0;while(pPath.top)if(Path.basenum.seat.row=row&Path.basenum.seat.col=col)/路徑某一步所在的位置return TRUE;num+;p+;re

36、turn FALSE;Status MazePath(MAZE M,SqStack *Path) / 若迷宮maze中從入口 start到出口 end的通道，則求得一條存放在棧中/ （從棧底到棧頂），并返回SUCCESS；否則返回FAILPosition curpos;int curstep;SElemType e,te;curpos=M.start; / 設(shè)定當(dāng)前位置為入口位置curstep=1; / 探索第一步/第一次查找路徑，設(shè)置5個(gè)方向(不遠(yuǎn)離!終點(diǎn)的五個(gè)方向)，若找到則返回SUCCESSdo if(Pass(M,curpos) / 當(dāng)前位置可通過(guò)，即是未曾走到過(guò)的通道塊 M.Maze

37、curpos.rowcurpos.col= ; / 留下足跡 e.direction=1; e.order=curstep; e.seat=curpos; Push(S,&e); / 加入路徑 if(curpos.row=M.end.row&curpos.col=M.end.col) / 到達(dá)終點(diǎn)（出口） return SUCCESS; curpos=NextPos(curpos,1); / 下一位置在當(dāng)前位置的右下方 curstep+; / 探索下一步 else / 當(dāng)前位置不能通過(guò) if(!StackEmpty(S) Pop(S,&e); while(e.direction=5&!Stac

38、kEmpty(S) M.Mazecurpos.rowcurpos.col= ;/標(biāo)記不能通過(guò) Pop(S,&e); / 留下不能通過(guò)的標(biāo)記，并退回一步 / while if(e.direction5) e.direction+; GetTop(S,&te); if(e.direction=5&te.direction=2) Pop(S,&e); e.direction+; Push(S,&e); / 換下一個(gè)方向探索 curpos=NextPos(e.seat,e.direction); / 當(dāng)前位置設(shè)為新方向的相鄰塊 / if / if / elsewhile(!StackEmpty(S);

39、curpos=M.start; / 設(shè)定當(dāng)前位置為入口位置curstep=1; / 探索第一步/如果第一次查找無(wú)結(jié)果則再進(jìn)行一次八個(gè)方向的查找，檢查是否存在第一次查找不到的特殊情況do if(Pass(M,curpos) / 當(dāng)前位置可通過(guò)，即是未曾走到過(guò)的通道塊 M.Mazecurpos.rowcurpos.col= ; / 留下足跡 e.direction=1; e.order=curstep; e.seat=curpos; Push(S,&e); / 加入路徑 if(curpos.row=M.end.row&curpos.col=M.end.col) / 到達(dá)終點(diǎn)（出口） /PrintPath(maze,S);/輸出路徑 return SUCCESS; curpos=NextPos(curpos,1); / 下一位置是當(dāng)前位置的東鄰 curstep+; / 探索下一步 else / 當(dāng)前位置不能通過(guò) if(!StackEmpty(S) Pop(S,&e);