2023年迷宫实验报告

一、实验内容

3、迷宫问题。假设迷宫由m行n列构成，有一个出口和一个入口，入口坐标为(1,1),出口

坐标为(m,n),试设计并验证以下算法：找出一条从入口通往出口的途径，或报告一个“无

法通过”的信息。

(1)用C语言实现顺序存储队列上的基本操作，然后运用该队列的基本操作找出迷宫

的一条最短途径。

(2)设计一个二维数组MAZE[m+2][n+2]表达迷宫，数组元素为0表达该位置可以

通过，数组元素为1表达该位置不可以通行。MAZE[1][1],MAZE[m][n]分别为迷宫的

入口和出口。

(3)输入迷宫的大小m行和n歹！I,动态生成二维数组；由随机数产生0或1,建立迷宫,

注意m*n的迷宫需要进行扩展，扩展部分的元素设立为1,相称于在迷宫周边布上一圈不准通

过的墙。

(4)规定输出模拟迷宫的二维数组;若存在最短途径，则有出口回溯到入口(出队列并运

用栈实现)，再打印从入口到出口的这条途径，例如(1,1),............(i,j)...........(m,n);

若没有途径，则打印“Nopath”。

(5)迷宫的任一位置(i,j)上均有八个可移动的方向，用二维数组Direction存放八个

方向的位置偏移量。

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

{」/}}；

(6)为避免出现原地踏步的情况需要标志已经通过的位置，采用一个标志数组MAR

K[m+2][n+2],初值均为0,在寻找途径的过程中，若通过了位置(i,j)，则将MARK[i]

lj]置为1。

(7)为了记录查找过程中到达位置(i,j)及初次到达(i,j)的前一位置(i_pre,j_pre),

需要记住前一位置(i_pre,j_pre)在队列中的序号pre,即队列中数据元素应当是一个三

元组(i,j,pre),

（8）搜索过程简朴下：将入口MAZE"][1]作为第一个出发点，依次在八个方向上

搜索可通行的位置,将可通行位置（i,j,pre）入队，形成第一层新的出发点，然后依次出队，即

对第一层中各个位置分别搜索它所在八个方向上的可通行位置，形成第二层新的出发点，…,

如此进行下去，直至达成出口MAZE[m]ln]或者迷宫所有位置都搜索完毕为止。

二、实验过程及结果

一、需求分析

1、用栈的基本操作完毕迷宫问题的求解，其中栈的基本操作作为一个独立的模块存在。

2、以二维数组M[m+2][n+2]表达迷宫,MEi][j]表达迷宫中相应（i,j）位置的

通行状态（0：表达可以通行，1：表达有墙，不可通行），完毕迷宫的抽象数据类型，涉及出

口、入口位置等。

3、用户从屏幕上输入迷宫，从键盘输入迷宫的大小，即迷宫的长和宽（由于控制台大

小限制，输入的长宽需在50以下），完毕相应迷宫的初始化。根据键盘输入的迷宫规格随机

生成大小相同的迷宫，产生方块的地方为墙，无方块的地方可通过，如下例所示：

如下所示:

■习软件、MicrosoftVisualStudio\Debug^3^Ht5i^«.e

PleaseinputthelengthandwidthoftheMAZE：

length<0<length<=50>：12

width<0<width<=50>：12

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

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

4、程序完毕对迷宫途径的搜索，为了更好地显示出求解结果，假如存在途径，则以长方形

形式将迷宫打印出来，而不是只按步输出坐标，也便于检查途径的对的性，用特定符号标出

迷宫的物理状态，其中字符表达出口和入口，标记出可行的途径；假如程序完毕

搜索后没有找到通路，则提醒用户“NoPath!”。如图所示：

5、程序执行的命令:

⑴创建初始化迷宫；

⑵搜索迷宫;

⑶输出搜索到的最短途径。

二、概要设计

(按照题目规定应当用队列实现途径的存储，但操作过程中碰到很多困难未能解决，故选择栈

的操作来实现途径的存储)

1、迷宫的抽象数据类型定义：

ADTMaze{

数据对象：D：={aij,Start,end卜20<=aij<20,Start,ende{(i,j)|0WiWm+2,0

WjWn+2,m,n20}}

数据关系：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已经定义，M的下属单元二维数组M.Maze[row+2][d+2]已存在,

M.start,M.end也已作为下属存储单元存在

操作结果:构成数据迷宫，用数值标记迷宫的物理状态，以0表达通路，以1表达障碍,

由终端读取迷宫空间大小，各点处的具体物理状态及Start和End点位置，完毕迷宫构建

Pass(M,CurPos)

初始条件:已知目前迷宫状态及当前位置

操作结果:完毕相应的搜索任务，假如可行,则返回1

NextPos(CurPos,directionr)

操作结果：返回CurPOS位置在方向direction上的下一位置

SameSeat(Path,row,col)

操作结果：若(row,col)位置是途径Path中的一个点,则返回TRUE

PrintMaze(M)

初始条件:迷宫M已存在

操作结果：输出字符标示的迷宫

MazePath(M,&Path)

初始条件:迷宫M已存在

操作结果：搜索迷宫，用palh返回搜索所得途径。如不存在，返回0

PrintPath(M,Path)

初始条件：迷宫M已存在

操作结果：迷宫M存在可行途径则将迷宫M及相应最短途径一起打印输出

}ADTMAZE；

3.本程序模块结构

(1)主函数模块

voidmain(){

初始化迷宫和栈；

创建迷宫：

输出迷宫；

搜索途径；

输出途径；

)

⑵栈模块一一实现栈抽象数据类型；

⑶迷宫模块一一实现迷宫抽象数据类型；

各模块之间的调用关系如下：

主程序模块

迷宫模块

栈模块

三、具体设计

1、基本数据类型操作

⑴栈模块

①typedefstruct{

intorder;

ePositionseat;

“ntdirection;

}SEIemiype;//步数、方向及位置

//栈定义

②typedefstructlnode{

SElemType*base;

SElemType*top;〃设两指针便于判断栈是否为空

intstacksize;//栈当前可使用的最大容量

}SqStack;

③参数设立：

#defineSTACKJNIT_SIZE100

#defineSTACKINCRENT10

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

StatusInitStack(SqStack&s){//构造一个空栈

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

if(!S上ase)exit(OVERLOW)；//存储分派失败

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){//栈满追加存储空间

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

ICREMENT)Sizeof(Selemtype));

if(!S.base)exit(OVERFLOW)〃存储分派失败

S.top=S.base+S.stacksize;//拟定新的栈顶指针

S.stacksize+=STACKINCREMENT;//已分派空间增长

)

*S.top++=*e；

returnok；

)

StatusPop(Sqstack&s,Se1emType&e){

//若栈不变，则删除栈顶元素，用e返回其值及ok,否则false

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

returnERROR;

*e=*--S.top；//顶指针减小，用e返回其数据

returnok；

)

⑵迷宫模块：

①迷宫的数据类型

#defineMAXLENGTH50//迷宫的最大长度

#defineMAXWIDTH50//屏幕宽度，迷宫的最大宽度

〃元素类型

typedefintStatus;

typedefstruct{

introw；

intco1；

}Position;。//位置坐标

〃迷宫定义

typedefintElemType;

typedefstructMAZE{

ElemTypeMaze[MAXLENGTH][MAXWIDTH]；。//迷宫的物理状

态描述

intlength,width；//迷宫的大小

oPositionstart,end；//开始与结束位置与栈的单元类型相同

JMAZE;//“迷宫”型数据

②迷宫模块中的基本操作

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；。//设立迷宫围墙

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

。(

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

oM->Maze[j][k]=rand()%2;。//随机生成迷宫

}

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；〃入口和出口设立*/

)

voidPrintMaze(MAZEM){〃打印出迷宫，涉及边界

prinlf("迷宫入口:[l,l]一用#表达\n”)；

printf("迷宫出口:[%d,%d1用#表达\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'#入口和出口用#表达

8?e1se

u

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

°)

printf(H\nM);

}//用字符型打印输出(i,j)状态

)

StatusPass(MAZEM,PositionCurPos){

//判断迷宫中当前位置CurPos上能否通过

//假如通过返回1

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

return1;〃假如当前位置是可以通过，返回1

e1sereturn0;//其它情况返回0

)

PositionNextPos(PositionCurPos,intdirection){

〃返回当前位置在direction方向上的下一位置

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

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

returnReturnPos;

)

StatusSameSeat(SqStackPath,introw,intcol){

//位置(row,col)在途径中时返回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；//设定”当前位置“为“入口位置”

curstep=l;//探索第一步

〃第一次查找途径，设立5个方向(不远离!终点的五个方向)，若找到则返回

SUCCESS

讨o{

oif(Pass(M,curpos)){//当前位置可通过，即是未曾走到过的通道块

。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){

。//到达终点(出口)

。returnSUCCESS;

0}

curpos=NextPos(curpos,l)；//下一位置在当前位置的

右下方

curstep++；//探索下一步

}

。else{〃当前位置不能通过

。。if(!StackEmpty(S)){

。Pop(S,&e);

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

。M.Maze[curpos.row][curpos.col]-'；〃标记不能通过

。。Pop(S,&e)；//留下不能通过的标记，并退回一步

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);//换下一个方向探索

。curpos=NextPos(e.seat,e.direction);//当前位置设为新

方向的相邻块

。。}//if

。}//if

}//eIse

}while(!StackEmpty(S));

curpos=M.start；//设定”当前位置"为“入口位置”

照urstep=1;〃探索第一步

//假如第一次查找无结果则再进行一次八个方向的查找,检查是否存在第一次

查找不到的特殊情况

0do{

if(Pass(M,curpos)){//当前位置可通过，即是未曾走到过的通道块

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//到达终点(出口)

//PrintPath(maze,S);。//输出途径

returnSUCCESS;

°}

bcurpos=NextPos(curposj)；//下一位置是当前位置的东

邻

curstep++;//探索下一步

)

0else{//当前位置不能通过

if(!StackEmpty(S)){

Pop(S,&e);

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

。M.Maze[curpos.row][curpos.col]-'；〃标记不能通过

6Pop(S,&e);//留下不能通过的标记，并退回一步

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)；//换下一个方向探索

。curpos=NextPos(e.seat,e.direction);//当前位置设为新方向

的相邻块

。。。}//if

。}//if

}//else

}while(!StackEmpty(S));

6returnFAIL;

}//MazePath

voidPrintPath(MAZEM,SqStackPath){//将迷宫及途径一起打印

if(StackEmpty(&Path)){

叩rinlf(”NoPath!\n");//途径栈为空，则提醒无途径

。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")；

)

)

⑶主函数算法：

voidmain(){

oMAZEM；

qStackpath;

InitStack(&path)；

<>SetMaze(&M);

®PrintMaze(M);

«>MazePath(M,&path);

PrintPath(M,path)；

)

2.函数的调用关系反映了本演示程序的层次结构

main1

丁佐桂港方迷宫德海

InitStackMazePathPrintPathPrintMazePassSetMaze

SameSeatNextPos

PushGetTopPop

StackEmpty

四、调试分析

1、开始没有将start.end设立为MAZE型数据的下属单元，使得各个迷

宫操作的函数参数十分散杂，调试时各参数关系不易把握。

2、另行设立PrintPath函数，使得终端输出更加和谐，并巧妙地将迷宫以特殊、明朗

的字符输出，效果更好。

3、开始出栈入栈的条件没有控制好，导致输出时不是完整途径，甚至犯错。

4、选择方向时有一定策略，开始选择时按照顺时针依次读取方向，发现太耗时且效果不

好,容易出现不必要的弯折走法，后来通过控制方向顺序，即第一方向为东南方，然后再

东方、南方…，选取越靠近出口的方向为优先方向，由于这样的话搜索途径时自然会本着

途径最短的原则向出口处行进，那么找到的途径自然是最短途径（之一）。

5、由于八个方向的特殊性，根据方向的顺序及索途径时仍会出现多走的情况，比如先往

东再往西南，其实是可以直接往南的，因此为了避免这种情况，在入栈时还要先进行这

种情况的判断，如是这种情况则出栈将前一位置方向改变再入栈。

6、为了便于找到最短途径，起初只使用了靠近出口处的五个方向,但是发现有特殊情况

存在时由于不能想远离出口的方向行进而找不到途径，因此在搜索途径时进行了两次搜

索，第一次使用五个靠进出口的方向搜索，找到途径时则返回SUCCESS,若未搜索

到则再进行一次八个方向的搜索，即为了防止漏掉特殊情况,找届时则返回SUCCESS,

由于第一搜索无结果若第二次搜索到途径也只能是特殊情况，故也应当是最短途径（之

一）。

7、最大的问题是并没有按照题目规定来做,由于题目中规定用队列来存储途径，通过实验

发现有很多问题难以解决，故选择了只用栈的方法来实现。

五、用户说明

1.本程序的运营环境为windows7（64位）操作系统，执行文献为数据结构迷宫.e

xe;

2.进入演示程序后,即显示对话形式的提醒操作过程，

1、提出输入迷宫的大小

2、按enter键输出随机生成的迷宫

3、按enter键开始搜索途径

搜索结果：

ThePath：输出迷宫及途径或者输出NoPath!

3.提醒输入迷宫大小后，用户输入所要解决迷宫的长r。w,宽col；

4.提醒输入迷宫后，用户将迷宫输入,0代表可行，1代表障碍；

5.按任意键开始后,程序自动进行对所建迷宫的搜索，并将搜索结果；

6.按任意键退出程序。

六、测试结果

1、无途径:

■习软件'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；〃位置坐标

typedefstruct{

®intorder;

oPositionseat；

intdirection;

}SElemType;//步数、方向及位置

〃栈定义

typedefstructInode{

SElemType*base;

SElemType*top;//设两指针便于判断栈是否为空

intstacksize;〃栈当前可使用的最大容量

}SqStack;

//迷宫定义

typedefintElemType;

typedefstructMAZE{

E1emTypeMaze[MAXLENGTH][MAXWIDTH];

ointlength,width；

0Positionstart,end；

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

//栈操作函数声明

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

StatusStackEmpty(SqStack*S)；//判空

StatusGetTop(SqStack*s,SElemType*e)；〃取栈顶元素

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

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

//迷宫操作函数说明

voidSetMaze(MAZE*M);。/*设立迷宫，随机生成*/

voidPrintMaze(MAZEM);。/*输出迷宫*/

StatusPass(MAZEM,PositionCurPos)；〃判断当前位置是否可通

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

StatusSameSeat(SqStackPath,introw,intcol);//找到迷宫中可行途径的各个位置

StatusMazePath(MAZEM,SqStack*Path);//搜索迷宫途径

voidPrintPath(MAZEM,SqStackPath);//若迷宫M存在可行途径则将该途径在迷宫

中输出

//主函数

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;“/设立迷宫围墙

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

°{

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

M->Maze[j][k]=rand()%2;。〃随机生成迷宫

)

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；//入口和出口设立*/

)

voidPrintMaze(MAZEM){

introw,col;

叩rintf("迷宫入口:[1,1]——用#表达\n")；

printf("迷宫出口:1%4%打一-用#表达\广\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("〃入口和出口用#表达

。。吒Ise

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

0)

®printf(M\nn)；

°)

)

StatusPass(MAZEM,PositionCurPos){

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

return1;//假如当前位置是可以通过，返回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}};//按一定顺序依次设立八个方向

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;//设定”当前位置“为“入口位置”

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

。〃第一次查找途径，设立5个方向(不远离!终点的五个方向)，若找到则返回SUCCESS

do{

if(Pass(M,curpos)){//当前位置可通过，即是未曾走到过的通道块

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){

//到达终点(出口)

returnSUCCESS；

0)

“curpos=NextPos(curpos,1);//下一位置在当前位置的右下方

curstep++;//探索下一步

0)

else{//当前位置不能通过

if(!StackEmpty(S)){

Pop(S,&e)；

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

。M.Maze[curpos.row][curpos.co1]='标记不能通过

。Pop(S,&e);//留下不能通过的标记，并退回一步

。。。}//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)；〃换下一个方向探索

curpos=NextPos(e.seat,e.direction)；//当前位置设为新方向的相

邻块

}//if

。}//if

。}//else

“while(!StackEmpty(S));

curpos=M.start;//设定”当前位置"为“入口位置"

ocurstep=l;//探索第一步

。〃假如第一次查找无结果则再进行一次八个方向的查找，检查是否存在第一次查找不到的特

殊情况

0do{

if(Pass(M,curpos)){//当前位置可通过，即是未曾走到过的通道块

。。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){

//到达终点(出口)

川//PrintPath(maze,S)；//输出途径

。。。returnSUCCESS;

3)

3curpos=NextPos(curpos,1);//下一位置是当前位置的东邻

curstep++;/