数据结构迷宫问题

【问题描述】以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫，求出一条从入「I到出门的通路。或得出没有通路的结论【基本要求】【测试数据】【实现提示】使用穷举法和栈求解【代码过程】lo//base.h//公用的常量和类型#iiiclude<stdio.h>#iiiclude<malloc.h>#iiiclude<stdlib.h>#iiiclude<string.h>//函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0-1//函数的返回值〃下一个通道方向〃迷宫大小#defineINFEASIBLE#defineOVERFLOW-2typedefintStatus;typedefintDirectiveType;#define-1//函数的返回值〃下一个通道方向〃迷宫大小//stack.h#defineSTACK_NT_SIZE100#defineSTACKINCREMENT10//栈的顺序存储实现typedefstruct...{hitrow;hitcol;}PosType;typedefstruct...{mtstep;〃当前位置在路径上的”序号”PosTypeseat;〃当前的坐标位置DirectiveTypedi;〃往下一个坐标位置的方向}SElemType;typedefstruct...{SElemType*base;SElemType*top:mtstacksize;JSqStack;//栈的基本操作的算法实现StatusIiutStack(SqStacks.base=(SElemType*)nialloc(STACK_INIT_SIZE*sizeof(SElemType));if(!s.base)exit(OVERFLOW);s.top=s.base;s.stacksize=STACKINITSIZE:——zreturnOK;}StatusGetTop(SqStacks,SElemType&e)...(if(s.top==s.base)retuniERROR:e=*(s.top-l);returnOK;}StatusPush(SqStack&s,SElemTypee)...(if(s.top-s.base>=s.stacksize)...(〃栈满，追加存储空间(SElemTypes.base=*)realloc(s.base,(s.stacksize-rSTACKINCREMENT)*sizeof(SElemType));if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;(SElemType}*s.top++=e;returnOK;

StatusPop(SqStack&s,SElemTypeif(s.top=s.base)retuinERROR;e=*—s.top;returnOK;}mtStackEmpty(SqStacks)freturns.base=s.top;}StatusCleaiStack(SqStack&s)fs.top=s.base;returnOK;}〃〜3oAinaze.h//迷宫程序件*〃**************************************************************迷宫问题算法：从入11出发，顺着某一个方向进行探索，若能走通,则继续前进;否则沿着原路退回，换一个方向继续探索,直至出11位置，求得一条通路，假如所有可能的通路都探索到而未能达到出11,则所设定的迷宫没有通路.说明:可通：未增走到过的通道快.*********************************************************/〃迷宫的行数〃迷宫的列数#defineROW9#defineCOL8typedef〃迷宫的行数〃迷宫的列数mtm.n;mtan[RANGE][RANGE];}MazeType;〃迷宫类型StatusIiiitMaze(MazeType&maze,inta[][COL],introw,mtcol)...{〃按照用户输入的row行和col列的二维数组(0/1)//设置迷宫maze的初值，包括加上边缘一圈的值i=l;i<=row;i++)...(fbr(intj=1J<=colJ++)...(}〃加上围墙fdi(mtj=0;j<=col+lj++)...(maze.aiT[O][j]=maze.an[row+1][j]=1;}fbi(i=0;i<=row+1；i++)...{maze.aiT[i][O]=maze.an[i][col+1]=1;}maze.m=row,inaze.n=col;leturnOK;}StatusPass(MazeTypemaze,PosTypecuipos)...(〃判断当前节点是否通过letuinniaze.au[cuipos.iow][cuipos.col]==0;}StatusFootPiiiit(MazeType&maze,PosTypecuipos)...(〃留下足迹maze.aiT[cuipos.row][curpos.col]~leturnOK;}StatusMarkPriiit(MazeType&maze,PosTypecurpos)...(〃留下不能通过的标记maze.aiT[cuipos.row][curpos.col]=,@,;leturnOK;}SElemTypeCreateSElem(mtstep,PosTypepos,mtSElemTypee;e.step=step;e.seat=pos;e.di=di;returne;}PosTypeNextPos(PosTypecuipos,DiiectiveType〃返回当前节点的下一节点PosTypepos=curpos;switch(di)•・・icase1://东pos.col++;break;TOC\o"1-5"\h\zcase2:〃南pos.row++；break;case3:〃西pos.col--;break;case4:〃北pos.row--;break;}returnpos;}StatusPosEquare(PosTypeposl,PosTypepos2)...(〃判断两节点是否相等returnposLrow==pos2.row&&posl.col==pos2.col;}voidPriiitMaze(MazeTypemaze.iiitrowjntcol)...(〃打印迷宫信息i=l;iv=tow;i++)...{fbi(intj=1jv=col;j++)…{switch(maze.an[i][j])-(case0:prmtf(nH);break;case*:M);break;casepnntf(”@”)；break;case1:prmtf(n#”)；break;)}pnntff”)；}}StatusMazePath(MazeType&maze,PosTypestart,PosTypeend)...{

〃求解迷宫maze中，从入IIstart到出IIend的一条路径〃若存在，返回TRUE,否则返回FALSESqStacks;SElemTypee;IiutStack(s);PosTypecuipos=start;mtcurstep=1;〃探索第一部do...(if(Pass(niaze.curpos)〃如果当前位置可以通过，即是未曾走到的通道块FootPiiiit(maze,cuipos);〃留F足迹e=CreateSElem(curstep,cuipos,1);〃创建元素Push(s,e);returnTRUE;〃获得下一节点:当前位置的东邻〃探索下一步〃当前位置不能通过iRPosEquare(cuipos.end))cuipos=NextPos(cuipos,1);cuistepf)else...(if(!StackEmpty(s))…{Pop(s,e);wliile(e.di=4&&!StackEmpty(s))...(〃留下不能通过的标记,MarkPrmt(maze,e.seat);Pop(s,e);cuistep—;并退回一步)if(e.di<4)...(returnTRUE;〃获得下一节点:当前位置的东邻〃探索下一步〃当前位置不能通过〃留下不能通过的标记,cuipos=NextPos(e.seat,e.di);〃求下一个节点))}}wliile(!StackEmpty(s));returnFALSE;}4o//test.cpp#iiicludeHbase.hH#iiiclude“stack.h”#iiicludeHmaze.h,r**〃****************voidmain()mta[ROW][COL];printf(Menterthemaze'sdata:fbi(mti=0;i<ROW;i++)for(intj=0;j<COL;j++)•••{scaiif("%d",&a[i](j]);}}PosTypestart,end;start.row=1;stail.col=1;end.row=9;end.col=8;MazeTyp