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

一、實(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ì)列上的基本操作，然后運(yùn)用該隊(duì)列的基本操作找出迷宮

的一條最短途徑。

(2)設(shè)計(jì)一個(gè)二維數(shù)組MAZE[m+2][n+2]表達(dá)迷宮，數(shù)組元素為0表達(dá)該位置可以

通過(guò)，數(shù)組元素為1表達(dá)該位置不可以通行。MAZE[1][1],MAZE[m][n]分別為迷宮的

入口和出口。

(3)輸入迷宮的大小m行和n歹！I,動(dòng)態(tài)生成二維數(shù)組；由隨機(jī)數(shù)產(chǎn)生0或1,建立迷宮,

注意m*n的迷宮需要進(jìn)行擴(kuò)展，擴(kuò)展部分的元素設(shè)立為1,相稱于在迷宮周邊布上一圈不準(zhǔn)通

過(guò)的墻。

(4)規(guī)定輸出模擬迷宮的二維數(shù)組;若存在最短途徑，則有出口回溯到入口(出隊(duì)列并運(yùn)

用棧實(shí)現(xiàn))，再打印從入口到出口的這條途徑，例如(1,1),............(i,j)...........(m,n);

若沒(méi)有途徑，則打印“Nopath”。

(5)迷宮的任一位置(i,j)上均有八個(gè)可移動(dòng)的方向，用二維數(shù)組Direction存放八個(gè)

方向的位置偏移量。

Direction[8][2]={{0,1},{1,1},{0,-1},{-1,-1},{1{-1,0},

{」/}}；

(6)為避免出現(xiàn)原地踏步的情況需要標(biāo)志已經(jīng)通過(guò)的位置，采用一個(gè)標(biāo)志數(shù)組MAR

K[m+2][n+2],初值均為0,在尋找途徑的過(guò)程中，若通過(guò)了位置(i,j)，則將MARK[i]

lj]置為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)當(dāng)是一個(gè)三

元組(i,j,pre),

（8）搜索過(guò)程簡(jiǎn)樸下：將入口MAZE"][1]作為第一個(gè)出發(fā)點(diǎn)，依次在八個(gè)方向上

搜索可通行的位置,將可通行位置（i,j,pre）入隊(duì)，形成第一層新的出發(fā)點(diǎn)，然后依次出隊(duì)，即

對(duì)第一層中各個(gè)位置分別搜索它所在八個(gè)方向上的可通行位置，形成第二層新的出發(fā)點(diǎn)，…,

如此進(jìn)行下去，直至達(dá)成出口MAZE[m]ln]或者迷宮所有位置都搜索完畢為止。

二、實(shí)驗(yàn)過(guò)程及結(jié)果

一、需求分析

1、用棧的基本操作完畢迷宮問(wèn)題的求解，其中棧的基本操作作為一個(gè)獨(dú)立的模塊存在。

2、以二維數(shù)組M[m+2][n+2]表達(dá)迷宮,MEi][j]表達(dá)迷宮中相應(yīng)（i,j）位置的

通行狀態(tài)（0：表達(dá)可以通行，1：表達(dá)有墻，不可通行），完畢迷宮的抽象數(shù)據(jù)類型，涉及出

口、入口位置等。

3、用戶從屏幕上輸入迷宮，從鍵盤輸入迷宮的大小，即迷宮的長(zhǎng)和寬（由于控制臺(tái)大

小限制，輸入的長(zhǎng)寬需在50以下），完畢相應(yīng)迷宮的初始化。根據(jù)鍵盤輸入的迷宮規(guī)格隨機(jī)

生成大小相同的迷宮，產(chǎn)生方塊的地方為墻，無(wú)方塊的地方可通過(guò)，如下例所示：

如下所示:

■習(xí)軟件、MicrosoftVisualStudio\Debug^3^Ht5i^?.e

PleaseinputthelengthandwidthoftheMAZE：

length<0<length<=50>：12

width<0<width<=50>：12

迷宮入口：H,i］一用#表示—

迷宮出口：112,121一同*表小

4、程序完畢對(duì)迷宮途徑的搜索，為了更好地顯示出求解結(jié)果，假如存在途徑，則以長(zhǎng)方形

形式將迷宮打印出來(lái)，而不是只按步輸出坐標(biāo)，也便于檢查途徑的對(duì)的性，用特定符號(hào)標(biāo)出

迷宮的物理狀態(tài)，其中字符表達(dá)出口和入口，標(biāo)記出可行的途徑；假如程序完畢

搜索后沒(méi)有找到通路，則提醒用戶“NoPath!”。如圖所示：

5、程序執(zhí)行的命令:

⑴創(chuàng)建初始化迷宮；

⑵搜索迷宮;

⑶輸出搜索到的最短途徑。

二、概要設(shè)計(jì)

(按照題目規(guī)定應(yīng)當(dāng)用隊(duì)列實(shí)現(xiàn)途徑的存儲(chǔ)，但操作過(guò)程中碰到很多困難未能解決，故選擇棧

的操作來(lái)實(shí)現(xiàn)途徑的存儲(chǔ))

1、迷宮的抽象數(shù)據(jù)類型定義：

ADTMaze{

數(shù)據(jù)對(duì)象：D：={aij,Start,end卜20<=aij<20,Start,ende{(i,j)|0WiWm+2,0

WjWn+2,m,n20}}

數(shù)據(jù)關(guān)系：R={length,width}

?length={<ai_1j,aij>|ai-1,aijGDi=1,,,,,m+2,j=1,,,,,n+2}

owidth={<aij-l,aij>|aijaij-1eD)

基本操作：

SetMaze(&M)

初始條件：M已經(jīng)定義，M的下屬單元二維數(shù)組M.Maze[row+2][d+2]已存在,

M.start,M.end也已作為下屬存儲(chǔ)單元存在

操作結(jié)果:構(gòu)成數(shù)據(jù)迷宮，用數(shù)值標(biāo)記迷宮的物理狀態(tài)，以0表達(dá)通路，以1表達(dá)障礙,

由終端讀取迷宮空間大小，各點(diǎn)處的具體物理狀態(tài)及Start和End點(diǎn)位置，完畢迷宮構(gòu)建

Pass(M,CurPos)

初始條件:已知目前迷宮狀態(tài)及當(dāng)前位置

操作結(jié)果:完畢相應(yīng)的搜索任務(wù)，假如可行,則返回1

NextPos(CurPos,directionr)

操作結(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é)果：搜索迷宮，用palh返回搜索所得途徑。如不存在，返回0

PrintPath(M,Path)

初始條件：迷宮M已存在

操作結(jié)果：迷宮M存在可行途徑則將迷宮M及相應(yīng)最短途徑一起打印輸出

}ADTMAZE；

3.本程序模塊結(jié)構(gòu)

(1)主函數(shù)模塊

voidmain(){

初始化迷宮和棧；

創(chuàng)建迷宮：

輸出迷宮；

搜索途徑；

輸出途徑；

)

⑵棧模塊一一實(shí)現(xiàn)棧抽象數(shù)據(jù)類型；

⑶迷宮模塊一一實(shí)現(xiàn)迷宮抽象數(shù)據(jù)類型；

各模塊之間的調(diào)用關(guān)系如下：

主程序模塊

迷宮模塊

棧模塊

三、具體設(shè)計(jì)

1、基本數(shù)據(jù)類型操作

⑴棧模塊

①typedefstruct{

intorder;

ePositionseat;

“ntdirection;

}SEIemiype;//步數(shù)、方向及位置

//棧定義

②typedefstructlnode{

SElemType*base;

SElemType*top;〃設(shè)兩指針便于判斷棧是否為空

intstacksize;//棧當(dāng)前可使用的最大容量

}SqStack;

③參數(shù)設(shè)立：

#defineSTACKJNIT_SIZE100

#defineSTACKINCRENT10

//.....--基本操作的算法描述——一-------一一

StatusInitStack(SqStack&s){//構(gòu)造一個(gè)空棧

S.base=(SelemType)mal1oc(STACKJNIT_SIZE*SizeOf(SelemType))；

if(!S上ase)exit(OVERLOW)；//存儲(chǔ)分派失敗

S.top=S.base；

S.stacksize=STACKJNIT_SIZE；

returnok;

)

StatusStackEmpty(Sqstack&S){//若S為空返回TRUE,否則

返回FALSE

returnS.base==S,top;

)

StatusGetTop(SqStack&S,Se1emtype&e){

//棧不空，用e返回s的棧頂元素及OK,否則返回ERROR

if(S.top==S.base)returnERROR;

e=*(S.top-1)；

returnok;

StatusPush(Sqstack&S,SelemType&e){//插入元素e為新的棧頂元

素

if(S.top-S.base>=S.stacksize){//棧滿追加存儲(chǔ)空間

S.base=(SelemType)realloc(S.base,(S.stacksize+STACK

ICREMENT)Sizeof(Selemtype));

if(!S.base)exit(OVERFLOW)〃存儲(chǔ)分派失敗

S.top=S.base+S.stacksize;//擬定新的棧頂指針

S.stacksize+=STACKINCREMENT;//已分派空間增長(zhǎng)

)

*S.top++=*e；

returnok；

)

StatusPop(Sqstack&s,Se1emType&e){

//若棧不變，則刪除棧頂元素，用e返回其值及ok,否則false

if(S.top=o=S.base)

returnERROR;

*e=*--S.top；//頂指針減小，用e返回其數(shù)據(jù)

returnok；

)

⑵迷宮模塊：

①迷宮的數(shù)據(jù)類型

#defineMAXLENGTH50//迷宮的最大長(zhǎng)度

#defineMAXWIDTH50//屏幕寬度，迷宮的最大寬度

〃元素類型

typedefintStatus;

typedefstruct{

introw；

intco1；

}Position;。//位置坐標(biāo)

〃迷宮定義

typedefintElemType;

typedefstructMAZE{

ElemTypeMaze[MAXLENGTH][MAXWIDTH]；。//迷宮的物理狀

態(tài)描述

intlength,width；//迷宮的大小

oPositionstart,end；//開(kāi)始與結(jié)束位置與棧的單元類型相同

JMAZE;//“迷宮”型數(shù)據(jù)

②迷宮模塊中的基本操作

Statussemaze(MAZE&M){

Printf(aP1easeinputthelengthandwidthoftheMAZE");

sanf(arlength,width”);

for(k=0；k<width+2；k++)?

wM->Maze[0][k]=1;

。for(j=0;j<length+2;j++)

8M->Maze|jj[0

for(j=0;j<1ength+2;j++)

。M一〉Maze皿width+1]=1；

for(k=0;kVwidth+2;k++)

。oM->Maze[length+l][k]=1；。//設(shè)立迷宮圍墻

4or(j=1;j<=length;j++)

。(

for(k=1;k<=width;k++)

oM->Maze[j][k]=rand()%2;。//隨機(jī)生成迷宮

}

M->1ength=length;

M—>width=width；

<>M->start.row=1；

<>M->start.col=1；

M->end.row=M->1ength;

M—>end.col=M->width;。

<>M->Maze[M—>start.row][M->start.co1]=M->Maze[M—>end.row][M->end.

col]=0；〃入口和出口設(shè)立*/

)

voidPrintMaze(MAZEM){〃打印出迷宮，涉及邊界

prinlf("迷宮入口:[l,l]一用#表達(dá)\n”)；

printf("迷宮出口:[%d,%d1用#表達(dá)\n”,M.1ength,M.width);

?>for(row=0;row<M.length+2;row++){

ofor(col=0；co1<M.width+2；co1++){

if((row==1&&col==1)||(row==M.length&&col==M.width))

oprintff'#入口和出口用#表達(dá)

8?e1se

u

eMprintf(%c0,M.Maze[row][co1]);

°)

printf(H\nM);

}//用字符型打印輸出(i,j)狀態(tài)

)

StatusPass(MAZEM,PositionCurPos){

//判斷迷宮中當(dāng)前位置CurPos上能否通過(guò)

//假如通過(guò)返回1

if(M.Maze[CurPos.rowJ[CurPos.col]==0)

return1;〃假如當(dāng)前位置是可以通過(guò)，返回1

e1sereturn0;//其它情況返回0

)

PositionNextPos(PositionCurPos,intdirection){

〃返回當(dāng)前位置在direction方向上的下一位置

ReturnPos.row=CurPos.row+Directionfdirection-1][0];

ReturnPos.col=CurPos.co1+Direction[direction—1][1];

returnReturnPos;

)

StatusSameSeat(SqStackPath,introw,intcol){

//位置(row,col)在途徑中時(shí)返回TRUE

owhi1e(p<Path.top){

◎if(Path.base[num].seat.row==row&&Path.base[num].seat.col

==co1)//途徑某一步所在的位置

^returnTRUE;。

gnum++；

p++；

6returnFALSE；

)

StatusMazePath(MAZEM,SqStack*S){

。//若迷宮maze中從入口start到出口end的通道，則求得一條存放在棧中

//(從棧底到棧頂)，并返回SUCCESS；否則返回FAIL

curpos=M.start；//設(shè)定”當(dāng)前位置“為“入口位置”

curstep=l;//探索第一步

〃第一次查找途徑，設(shè)立5個(gè)方向(不遠(yuǎn)離!終點(diǎn)的五個(gè)方向)，若找到則返回

SUCCESS

討o{

oif(Pass(M,curpos)){//當(dāng)前位置可通過(guò)，即是未曾走到過(guò)的通道塊

。M.Maze[curpos.row][curpos.col]-,；//留下足跡

。e.direction=1;

。e.order=curstep;

e.seat=curpos；

。Push(S,&e);//加入途徑

if(curpos.row==M.end.row&&curpos.co1==M.end.col){

。//到達(dá)終點(diǎn)(出口)

。returnSUCCESS;

0}

curpos=NextPos(curpos,l)；//下一位置在當(dāng)前位置的

右下方

curstep++；//探索下一步

}

。else{〃當(dāng)前位置不能通過(guò)

。。if(!StackEmpty(S)){

。Pop(S,&e);

oowhile(e.direction==5&&!StackEmpty(S)){

。M.Maze[curpos.row][curpos.col]-'；〃標(biāo)記不能通過(guò)

。。Pop(S,&e)；//留下不能通過(guò)的標(biāo)記，并退回一步

go}//while

if(e.direction<5){

ge.direction++;

。。GetTop(S,&te);

川。if(e.direction==5&&te.direction==2){

8。Pop(S,&e);

e.direction++;

0)

。。Push(S,&e);//換下一個(gè)方向探索

。curpos=NextPos(e.seat,e.direction);//當(dāng)前位置設(shè)為新

方向的相鄰塊

。。}//if

。}//if

}//eIse

}while(!StackEmpty(S));

curpos=M.start；//設(shè)定”當(dāng)前位置"為“入口位置”

照urstep=1;〃探索第一步

//假如第一次查找無(wú)結(jié)果則再進(jìn)行一次八個(gè)方向的查找,檢查是否存在第一次

查找不到的特殊情況

0do{

if(Pass(M,curpos)){//當(dāng)前位置可通過(guò)，即是未曾走到過(guò)的通道塊

M.MazeLcurpos.row]Lcurpos.co1]=,'；//留下足跡

ge.direction=1;

oe.order=curstep;

0。e.seat=curpos;

dPush(S,&e);//加入途徑

°if(curpos.row==M.end.row&&curpos.col==M.end.co1){

e//到達(dá)終點(diǎn)(出口)

//PrintPath(maze,S);。//輸出途徑

returnSUCCESS;

°}

bcurpos=NextPos(curposj)；//下一位置是當(dāng)前位置的東

鄰

curstep++;//探索下一步

)

0else{//當(dāng)前位置不能通過(guò)

if(!StackEmpty(S)){

Pop(S,&e);

。whi1e(e.direction==8&&!StackEmpty(S)){

。M.Maze[curpos.row][curpos.col]-'；〃標(biāo)記不能通過(guò)

6Pop(S,&e);//留下不能通過(guò)的標(biāo)記，并退回一步

6。}//while

。if(e.direction<8){

°e.direction++;

egGetTop(S,&te);

oo。if(e.direction==4&&te.direction==2){

00Pop(S,&e)；

。e.direction++;

d0I

Push(S,&e)；//換下一個(gè)方向探索

。curpos=NextPos(e.seat,e.direction);//當(dāng)前位置設(shè)為新方向

的相鄰塊

。。。}//if

。}//if

}//else

}while(!StackEmpty(S));

6returnFAIL;

}//MazePath

voidPrintPath(MAZEM,SqStackPath){//將迷宮及途徑一起打印

if(StackEmpty(&Path)){

叩rinlf(”NoPath!\n");//途徑棧為空，則提醒無(wú)途徑

。exit(OVERFLOW)；

)

printf(H\nThePath:\nn);

for(row=0;row<M.1ength+2;row++){

for(co1=0;col<M.width+2;col++){

?if(SanieSeat(Path,row,co1)){

。if((row==l&&col==1)||(row==M.length&&col==M.width))

。sprintf("#")；

oelse

000叩rintf(">");

00num++;

叩++；

Odd|

。吒1se

。。printf(n%c",M.Maze[row][col]);

)

oprintf("\n")；

)

)

⑶主函數(shù)算法：

voidmain(){

oMAZEM；

qStackpath;

InitStack(&path)；

<>SetMaze(&M);

?PrintMaze(M);

?>MazePath(M,&path);

PrintPath(M,path)；

)

2.函數(shù)的調(diào)用關(guān)系反映了本演示程序的層次結(jié)構(gòu)

main1

丁佐桂港方迷宮德海

InitStackMazePathPrintPathPrintMazePassSetMaze

SameSeatNextPos

PushGetTopPop

StackEmpty

四、調(diào)試分析

1、開(kāi)始沒(méi)有將start.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)先方向，由于這樣的話搜索途徑時(shí)自然會(huì)本著

途徑最短的原則向出口處行進(jìn)，那么找到的途徑自然是最短途徑（之一）。

5、由于八個(gè)方向的特殊性，根據(jù)方向的順序及索途徑時(shí)仍會(huì)出現(xiàn)多走的情況，比如先往

東再往西南，其實(shí)是可以直接往南的，因此為了避免這種情況，在入棧時(shí)還要先進(jìn)行這

種情況的判斷，如是這種情況則出棧將前一位置方向改變?cè)偃霔！?/p>

6、為了便于找到最短途徑，起初只使用了靠近出口處的五個(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)當(dāng)是最短途徑（之

一）。

7、最大的問(wèn)題是并沒(méi)有按照題目規(guī)定來(lái)做,由于題目中規(guī)定用隊(duì)列來(lái)存儲(chǔ)途徑，通過(guò)實(shí)驗(yàn)

發(fā)現(xiàn)有很多問(wèn)題難以解決，故選擇了只用棧的方法來(lái)實(shí)現(xiàn)。

五、用戶說(shuō)明

1.本程序的運(yùn)營(yíng)環(huán)境為windows7（64位）操作系統(tǒng)，執(zhí)行文獻(xiàn)為數(shù)據(jù)結(jié)構(gòu)迷宮.e

xe;

2.進(jìn)入演示程序后,即顯示對(duì)話形式的提醒操作過(guò)程，

1、提出輸入迷宮的大小

2、按enter鍵輸出隨機(jī)生成的迷宮

3、按enter鍵開(kāi)始搜索途徑

搜索結(jié)果：

ThePath：輸出迷宮及途徑或者輸出NoPath!

3.提醒輸入迷宮大小后，用戶輸入所要解決迷宮的長(zhǎng)r。w,寬col；

4.提醒輸入迷宮后，用戶將迷宮輸入,0代表可行，1代表障礙；

5.按任意鍵開(kāi)始后,程序自動(dòng)進(jìn)行對(duì)所建迷宮的搜索，并將搜索結(jié)果；

6.按任意鍵退出程序。

六、測(cè)試結(jié)果

1、無(wú)途徑:

■習(xí)軟件'MicrosoftVisualStudio\Debug\SQ^§^迷宮.

PleaseinputthelengthandwidthoftheMAZE：

length<0<length<=50>：12

width<0<width<=50>：12

修宮入口：H,l］一用Jt表示—

族宮出口：H2,12］一同年小

@@@@@@@@@@@@@@

⑹??

n?00

QQ?

Q

@?

??

Q□Q

Q???

3Q?

?

QQ

jQ□□□

?0

3Q?

??0

30

?Q?0

QQ

QQ?QQ0

QQQ

?????0

@@@@

Path?

Pressanytocontinue

2、找到最短途徑:

PleaseinputthelengthandviidthoftheMAZE：

［length<0<length<=50>：15

^idth<0<width<=50>：16

圈宮入口:tia］一用*表示—

修宮出口：115,16］一用建不

@@@◎

Q?QQ

??00Q????

Q?????00?0

0??00?

??????0000000???Q

13

?000??

Q

>?

XK

Xz◎◎

Q??Q

◎

?QQ

?????

0Q◎

?Q?

◎

??0

QQ?Q◎

00???

QQQ◎

?Q?

0?Q

Q?0

?0???

Q>

Q?Q?

>

QQQ????

>@

0??

n

Q?Q?@Q????Q

?Q

ay

nytocontinue

七、附錄（源代碼及注釋）

#include"time.h"

#includestdio.h"

#include"stdlib.h',

#inc1udeuconio.h"

#defineNULL0

#defineTRUE1

#defineFALSE0

#defineSUCCESS1

#defineFAIL0

#defineOK1

#defineERROR0

#defineOVERFLOW-1

#defineINFEASIBLE-2

#defineMAXLENGTH50

#defineMAXWIDTH50

#defineSTACK_INIT_SIZE100

#defineSTACKINCRENT10

//元素類型

typedefintStatus;

typedefstruct{

ointrow;

intcol；

}Position；〃位置坐標(biāo)

typedefstruct{

?intorder;

oPositionseat；

intdirection;

}SElemType;//步數(shù)、方向及位置

〃棧定義

typedefstructInode{

SElemType*base;

SElemType*top;//設(shè)兩指針便于判斷棧是否為空

intstacksize;〃棧當(dāng)前可使用的最大容量

}SqStack;

//迷宮定義

typedefintElemType;

typedefstructMAZE{

E1emTypeMaze[MAXLENGTH][MAXWIDTH];

ointlength,width；

0Positionstart,end；

}MAZE；〃迷宮大小及出入口位置

//棧操作函數(shù)聲明

StatusInitStack(SqStack*S);//初始化

StatusStackEmpty(SqStack*S)；//判空

StatusGetTop(SqStack*s,SElemType*e)；〃取棧頂元素

StatusPush(SqStack*S,SElemType*e);//入棧

StatusPop(SqStack*s,SE1emType*e)；//出棧

//迷宮操作函數(shù)說(shuō)明

voidSetMaze(MAZE*M);。/*設(shè)立迷宮，隨機(jī)生成*/

voidPrintMaze(MAZEM);。/*輸出迷宮*/

StatusPass(MAZEM,PositionCurPos)；〃判斷當(dāng)前位置是否可通

PositionNextPos(PositionCurPos,intdirectionr);〃下一位置

StatusSameSeat(SqStackPath,introw,intcol);//找到迷宮中可行途徑的各個(gè)位置

StatusMazePath(MAZEM,SqStack*Path);//搜索迷宮途徑

voidPrintPath(MAZEM,SqStackPath);//若迷宮M存在可行途徑則將該途徑在迷宮

中輸出

//主函數(shù)

voidmain(){

oMAZEM;

?SqStackpath；

“nitStack(&path);

oSetMaze(&M);

PrintMaze(M);

0MazePath(M,&path);

3PrintPath(M,path);

)

〃迷宮操作

voidSetMaze(MAZE*M){

“nt1ength,width,j,k;

oprintf("Pleaseinputthe1engthandwidthoftheMAZE：\nlength

(0<length<=50):")；

?scanf(u%d”,&1ength);

叩rintf("width(0<width<=50):H)；

oscanf(0%d",&width);

srand((unsigned)time(NULL))；

?for(k=0;k<width+2;k++)。

M->Maze[OJ[k]=1;

。for(j=0;j<1ength+2;j++)

^M->Maze[j][0]=l;

?for(j=0;j<length+2;j++)

。。M->Maze[j][width+l]=1;

for(k=0；k<width+2;k++)

。oM—>Maze[1ength+1][k]=1;“/設(shè)立迷宮圍墻

6for(j=1;j<=length;j++)

°{

。for(k=l;k<=width;k++)

M->Maze[j][k]=rand()%2;?！S機(jī)生成迷宮

)

M—>length=length;

<>M->width=width；

oM->start,row=1;

◎M->start.col=l;

M->end.row=M->length;

oM->end.co1=M->width;

M->Maze[M->start,row][M->start.co1]=M—>Maze[M->end.row][M—>en

d.col]=0；//入口和出口設(shè)立*/

)

voidPrintMaze(MAZEM){

introw,col;

叩rintf("迷宮入口:[1,1]——用#表達(dá)\n")；

printf("迷宮出口:1%4%打一-用#表達(dá)\廣\4.怕1^111,\4.width);

ofor(row=0;row<M.length+2;row++){

。for(col=0;col<M.width+2；co1++){

。?if((row==l&&col==l)||(row==M.1ength&&col==M.width))

printf("〃入口和出口用#表達(dá)

。。吒Ise

。3printf(u%cM.Maze[row][col]);

0)

?printf(M\nn)；

°)

)

StatusPass(MAZEM,PositionCurPos){

if(M.Maze[CurPos.row][CurPos.co1]==0)

return1;//假如當(dāng)前位置是可以通過(guò)，返回1

eIsereturn0；//其它情況返回0

)

PositionNextPos(PositionCurPos,intdirection){

PositionReturnPos;

疝itDirection[8][2]={{1,1},{0,1},{1,O},{-1,1},{1,-1},{0,-1},{-1,0},{-1,-

1}};//按一定順序依次設(shè)立八個(gè)方向

oReturnPos.row=CurPos.row+Direction[direction-l][0]；

RetumPos.co1=CurPos.col+Direction[direction-1][1];

returnReturnPos;

)

StatusSameSeat(SqStackPath,introw,intco1){

?SElemType*p=Path.base;

intnum=O;

while(p<Path.top){

ooif(Path.base[num].seat.row==row&&Path.base[num].seat.col==col)//

徑某一步所在的位置

oreturnTRUE;。

num++;

0p++;

)

returnFALSE;

)

StatusMazePath(MAZEM,SqStack*Path){

。//若迷宮maze中從入口start到出口end的通道，則求得一條存放在棧中

“/(從棧底到棧頂)，并返回SUCCESS;否則返回FAIL

Positioncurpos；

?intcurstep;

oSElemTypee,te;

ocurpos=M.start;//設(shè)定”當(dāng)前位置“為“入口位置”

◎curstep=l;//探索第一步

?！ǖ谝淮尾檎彝緩?，設(shè)立5個(gè)方向(不遠(yuǎn)離!終點(diǎn)的五個(gè)方向)，若找到則返回SUCCESS

do{

if(Pass(M,curpos)){//當(dāng)前位置可通過(guò)，即是未曾走到過(guò)的通道塊

M.Maze[curpos.row][curpos.col]=''；//留下足跡

。e.direction=1;

Qe.order=curstep;

e.seat=curpos;

。。Push(S,&e);//加入途徑

if(curpos.row==M.end.row&&curpos.co1==M.end.col){

//到達(dá)終點(diǎn)(出口)

returnSUCCESS；

0)

“curpos=NextPos(curpos,1);//下一位置在當(dāng)前位置的右下方

curstep++;//探索下一步

0)

else{//當(dāng)前位置不能通過(guò)

if(!StackEmpty(S)){

Pop(S,&e)；

owhile(e.direction==5&&!StackEmpty(S)){

。M.Maze[curpos.row][curpos.co1]='標(biāo)記不能通過(guò)

。Pop(S,&e);//留下不能通過(guò)的標(biāo)記，并退回一步

。。。}//while

。。。if(e.direction<5){

se.direction++;

ggGetTop(S,&te);

。if(e.direction==5&&te.direction==2){

。?ePop(S,&e);

。。e.direction++;

000|

6ePush(S,&e)；〃換下一個(gè)方向探索

curpos=NextPos(e.seat,e.direction)；//當(dāng)前位置設(shè)為新方向的相

鄰塊

}//if

。}//if

。}//else

“while(!StackEmpty(S));

curpos=M.start;//設(shè)定”當(dāng)前位置"為“入口位置"

ocurstep=l;//探索第一步

?！偃绲谝淮尾檎覠o(wú)結(jié)果則再進(jìn)行一次八個(gè)方向的查找，檢查是否存在第一次查找不到的特

殊情況

0do{

if(Pass(M,curpos)){//當(dāng)前位置可通過(guò)，即是未曾走到過(guò)的通道塊

。。M.Maze[curpos.row][curpos.col]=,*;//留下足跡

e.direction=1;

。e.order=curstep;

e.seat=curpos;

。Push(S,&e);//加入途徑

。if(curpos.row==M.end.row&&curpos.co1==M.end.co1){

//到達(dá)終點(diǎn)(出口)

川//PrintPath(maze,S)；//輸出途徑

。。。returnSUCCESS;

3)

3curpos=NextPos(curpos,1);//下一位置是當(dāng)前位置的東鄰

curstep++;/