数据结构(C语言)迷宫问题

【问题描述】以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路。或得出没有通路的结论【基本要求】【测试数据】【实现提示】使用穷举法和栈求解【代码过程】1。//base.h//-------------------公用的常量和类型----------------------------#includestdio.h#includemalloc.h#includestdlib.h#includestring.h//函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;//函数的返回值typedefintDirectiveType;//下一个通道方向#defineRANGE100//迷宫大小//~2。//stack.h#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10//------------栈的顺序存储实现------------------------------typedefstruct...{introw;intcol;}PosType;typedefstruct...{intstep;//当前位置在路径上的序号PosTypeseat;//当前的坐标位置DirectiveTypedi;//往下一个坐标位置的方向}SElemType;typedefstruct...{SElemType*base;SElemType*top;intstacksize;}SqStack;//-----------------栈的基本操作的算法实现--------------------------------StatusInitStack(SqStack&s)...{s.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!s.base)exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_INIT_SIZE;returnOK;}StatusGetTop(SqStacks,SElemType&e)...{if(s.top==s.base)returnERROR;e=*(s.top-1);returnOK;}StatusPush(SqStack&s,SElemTypee)...{if(s.top-s.base=s.stacksize)...{//栈满，追加存储空间s.base=(SElemType*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;}*s.top++=e;returnOK;}StatusPop(SqStack&s,SElemType&e)...{if(s.top==s.base)returnERROR;e=*--s.top;returnOK;}intStackEmpty(SqStacks)...{returns.base==s.top;}StatusClearStack(SqStack&s)...{s.top=s.base;returnOK;}//~3。//maze.h//--------------------迷宫程序----------------------------------/**//**************************************************************迷宫问题算法:从入口出发,顺着某一个方向进行探索,若能走通,则继续前进;否则沿着原路退回,换一个方向继续探索,直至出口位置,求得一条通路,假如所有可能的通路都探索到而未能达到出口,则所设定的迷宫没有通路.说明:可通:未增走到过的通道快.*********************************************************/#defineROW9//迷宫的行数#defineCOL8//迷宫的列数typedefstruct...{intm,n;intarr[RANGE][RANGE];}MazeType;//迷宫类型StatusInitMaze(MazeType&maze,inta[][COL],introw,intcol)...{//按照用户输入的row行和col列的二维数组(0/1)//设置迷宫maze的初值,包括加上边缘一圈的值for(inti=1;i=row;i++)...{for(intj=1;j=col;j++)...{maze.arr[i][j]=a[i-1][j-1];}}//加上围墙for(intj=0;j=col+1;j++)...{maze.arr[0][j]=maze.arr[row+1][j]=1;}for(i=0;i=row+1;i++)...{maze.arr[i][0]=maze.arr[i][col+1]=1;}maze.m=row,maze.n=col;returnOK;}StatusPass(MazeTypemaze,PosTypecurpos)...{//判断当前节点是否通过returnmaze.arr[curpos.row][curpos.col]==0;}StatusFootPrint(MazeType&maze,PosTypecurpos)...{//留下足迹maze.arr[curpos.row][curpos.col]='*';returnOK;}StatusMarkPrint(MazeType&maze,PosTypecurpos)...{//留下不能通过的标记maze.arr[curpos.row][curpos.col]='@';returnOK;}SElemTypeCreateSElem(intstep,PosTypepos,intdi)...{SElemTypee;e.step=step;e.seat=pos;e.di=di;returne;}PosTypeNextPos(PosTypecurpos,DirectiveTypedi)...{//返回当前节点的下一节点PosTypepos=curpos;switch(di)...{case1://东pos.col++;break;case2://南pos.row++;break;case3://西pos.col--;break;case4://北pos.row--;break;}returnpos;}StatusPosEquare(PosTypepos1,PosTypepos2)...{//判断两节点是否相等returnpos1.row==pos2.row&&pos1.col==pos2.col;}voidPrintMaze(MazeTypemaze,introw,intcol)...{//打印迷宫信息for(inti=1;i=row;i++)...{for(intj=1;j=col;j++)...{switch(maze.arr[i][j])...{case0:printf();break;case'*':printf(*);break;case'@':printf(@);break;case1:printf(#);break;}}printf();}}StatusMazePath(MazeType&maze,PosTypestart,PosTypeend)...{//求解迷宫maze中,从入口start到出口end的一条路径//若存在,返回TRUE,否则返回FALSESqStacks;SElemTypee;InitStack(s);PosTypecurpos=start;intcurstep=1;//探索第一部do...{if(Pass(maze,curpos))...{//如果当前位置可以通过,即是未曾走到的通道块FootPrint(maze,curpos);//留下足迹e=CreateSElem(curstep,curpos,1);//创建元素Push(s,e);if(PosEquare(curpos,end))returnTRUE;curpos=NextPos(curpos,1);//获得下一节点:当前位置的东邻curstep++;//探索下一步}else...{//当前位置不能通过if(!StackEmpty(s))...{Pop(s,e);while(e.di==4&&!StackEmpty(s))...{MarkPrint(maze,e.seat);Pop(s,e);curstep--;//留下不能通过的标记,并退回一步}if(e.di4)...{e.di++;Push(s,e);//换一个方向探索curpos=NextPos(e.seat,e.di);//求下一个节点}}}}while(!StackEmpty(s));returnFALSE;}//~4。//test.cpp#includebase.h#includestack.h#includemaze.h/**//****************测试***********************************/voidmain()...{inta[ROW][COL];printf(enterthemaze'sdata:);for(inti=0;iROW;i++)...{for(intj=0;jCOL;j++)...{scanf(%d,&a[i][j]);}}PosTypestart,end;start.row=1;start.col=1;end.row=9;end.col=8;MazeTypemaze;InitMaze(maze,a,ROW,COL);Statusok=MazePath(maze,start,end);if(ok)PrintMaze(maze,ROW,COL);elseprintf(没有找到通路);}//~本文来自:中国自学编程网()详细出处参考：