C语言数据结构之迷宫求解问题
现在网上各种对于迷宫的求解,版本多的数不胜数。本人小白一枚,贴上自己对迷宫的求解这个小项目,自己写的。望能帮助一些同样有困难的人,毕竟我当时费解了好一会儿时间呢。
首先,先标明对于迷宫求解这个项目,首先我提出自己的思路,利用“穷举求解”的方法(严蔚敏老师数据结构一书中提到,一开始不知方法其名。)其实简单来说就是一条路一条路去试,当然不能随便试,我的方法是按照从入口出发,顺一个方向向前探索,走得通就继续向前走;否则留下标记沿原路退回并换一个方向继续探索,直到所有的路都走完为止。还是用栈的先进后出的结构保存一路的路线。代码用到了栈的顺序实现数组格式的结构(对于栈并没有详细阐述)。
//调用头文件 #ifndefAFXSTD_H #defineAFXSTD_H #include#include #include #include usingnamespacestd; //cout;cin;C++的输入输出 #endif
//迷宫的结构体的创建 #ifndefMAZE_H #defineMAZE_H #defineROWSIZE10//迷宫大小 #defineCOLSIZE10 #defineReachable0//可以到达的结点 #defineBar1//障碍物 #defineFoot2//足迹 #defineMark3//不可通路标记 typedefintMapType[ROWSIZE][COLSIZE];//地图类型 typedefstruct { introw;//x intcol;//y; }PosType;//坐标结构体 typedefstruct { intord;//通道块在道路上的序号 PosTypeseat;//小人坐标 intdi;//方向//1234 }MElemType;//试迷宫小人的结构 typedefMElemTypeSElemType;//和stack关联 boolMazePass(MapTypemaze,PosTypecurpos); voidFootPrint(MapTypemaze,PosTypecurpos);//足迹打印 PosTypeNextPos(PosTypecurpos,intdi);//下一个位置 voidMarkPrint(MapTypemaze,PosTypecurpos);//打印不可通标记 boolMazePath(MapTypemaze,PosTypestart,PosTypeend);//迷宫解谜核心 voidPrintMap(MapTypemaze);//打印地图 #endif
//栈的结构体 #include"Maze.h" #ifndefSEQSTACK_H #defineSEQSTACK_H #defineSTACKSIZE100 //typedefintSElemType; structSeqStack { SElemType*data; intmaxsize; inttop; }; voidInit_Stack(SeqStack&st); voidDestroy_Stack(SeqStack&st); voidStack_Clear(SeqStack&st); boolStack_Empty(SeqStack&st); boolStack_Full(SeqStack&st); intStack_Size(SeqStack&st); boolStack_Push(SeqStack&st,constSElemType&x); boolStack_Pop(SeqStack&st,SElemType&x); SElemTypeGetTop(SeqStack&st); voidPop(SeqStack&st); #endif
以上是头文件的创建,和结构体的创建,现在真的深切感到结构体的重要性。结构体创建不好就是自己给自己挖坑,切记切记!!
现在贴出函数的代码,解释我会尽力都写清楚。(栈的问题我后续会重新再仔细阐述的,这次的重点在于迷宫的求解,所以直接贴出栈的详细代码,望谅解。)
//这里是栈的实现代码 #include"AfxStd.h" #include"Stack.h" boolStack_Resize(SeqStack&st) { SElemType*s=(SElemType*)malloc(sizeof(SElemType)*st.maxsize*2); if(NULL==s)returnfalse; for(inti=0;i<=st.top;++i) { s[i]=st.data[i]; } free(st.data); st.data=s; st.maxsize=st.maxsize*2; returntrue; } voidInit_Stack(SeqStack&st) { st.maxsize=STACKSIZE; st.top=-1; st.data=(SElemType*)malloc(sizeof(SElemType)*st.maxsize); if(NULL==st.data) { exit(0); } } voidDestroy_Stack(SeqStack&st) { free(st.data); st.data=NULL; st.maxsize=0; st.top=-1; } voidStack_Clear(SeqStack&st) { st.top=-1; } boolStack_Empty(SeqStack&st) { returnStack_Size(st)==0; } boolStack_Full(SeqStack&st) { returnStack_Size(st)==st.maxsize; } intStack_Size(SeqStack&st) { returnst.top+1; } boolStack_Push(SeqStack&st,constSElemType&x) { if(Stack_Full(st)&&!Stack_Resize(st)) { returnfalse; } st.data[++st.top]=x; returntrue; } boolStack_Pop(SeqStack&st,SElemType&x) { if(Stack_Empty(st)) { returnfalse; } x=st.data[st.top--]; returntrue; }
//调用前面创建的头文件 #include"AfxStd.h" #include"Maze.h" #include"Stack.h" ///////////////////////////////////////////////// boolMazePass(MapTypemaze,PosTypecurpos)//判断是否可以通过 { returnmaze[curpos.row][curpos.col]==Reachable;//判断当前结点是否能通过 } voidFootPrint(MapTypemaze,PosTypecurpos)//打印足迹 { maze[curpos.row][curpos.col]=Foot; } PosTypeNextPos(PosTypecurpos,intdi)//对下一个结点方向的判断 { switch(di) { case1:curpos.row+=1;break;//1 case2:curpos.col-=1;break;//2 case3:curpos.row-=1;break;//3 case4:curpos.col+=1;break;//4 } returncurpos; } voidMarkPrint(MapTypemaze,PosTypecurpos)//不能通过的结点留下不能通过的标记 { maze[curpos.row][curpos.col]=Mark; } boolMazePath(MapTypemaze,PosTypestart,PosTypeend)//(核心)迷宫解谜 { boolres=false;//定义一个res参数为布尔型 PosTypecurpos=start;//初始当前位置为入口 intcurstep=1;//初始探索方向为1 SeqStackst;//路径存储栈 MElemTypee;//初始探索小人 Init_Stack(st);//初始化栈 do{ if(MazePass(maze,curpos))//当前位置可通过,即是未曾走到过的坐标 { FootPrint(maze,curpos);//留下足迹 e.di=1,e.seat=curpos,e.ord=curstep++; Stack_Push(st,e);//加入路径中 if(curpos.row==end.row&&curpos.col==end.col) { res=true; break; }//到达终点 curpos=NextPos(curpos,1);//探索下一位置 } else { if(!Stack_Empty(st))//当前位置不能通过 { Stack_Pop(st,e); while(e.di==4&&!Stack_Empty(st)) { MarkPrint(maze,e.seat); Stack_Pop(st,e);//留下不能通过的标记,并退回一步 } if(e.di<4) { e.di+=1;//换下一个方向探索 Stack_Push(st,e);//再次记录路径 curpos=NextPos(e.seat,e.di);//当前位置设为新方向的相邻块 } } } }while(!Stack_Empty(st));//当栈空摧毁栈,返回失败参数 Destroy_Stack(st); returnres; } voidPrintMap(MapTypemaze)//打印地图 { for(inti=0;i以上就是迷宫的详细解释,希望能帮助到大家。后面再添加我的测试文件。
#include"AfxStd.h" #include"Maze.h" intmain() { MapTypemaze={//一开始地图的创建 {1,1,1,1,1,1,1,1,1,1}, {1,0,1,1,1,1,1,1,1,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,1,1,1,1,0,1}, {1,0,0,0,1,1,1,1,0,1}, {1,0,1,1,1,1,0,0,0,1}, {1,0,1,1,1,1,1,1,1,1}, {1,0,0,0,0,0,0,1,1,1}, {1,0,1,1,1,1,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1}, }; PosTypestart={1,1},end={8,8}; PrintMap(maze);//打印初始地图 MazePath(maze,start,end); PrintMap(maze);//打印迷宫解法 return0; }以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。