迷宫问题课程设计报告

课程设计报告课程设计题目：小组成员何保平（201420180408）蔡聪聪（201420180409）吴俊文（201420180410）班级1421804专业软件工程指导教师高永平2016年01月05日一、任务可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出。二、问题分析迷宫问题采用试探法求解，即从入口出发，在当前位置任选一个方向向前试探，若下一位置可通（即该位置为从未走过的通道块）则继续试探行进；若当前位置的所有方向均不通（为墙体或已走过的通道块）时，则按原路返回上一位置，重新选择其他方向继续试探前进。这样不断试探前进，知道到达迷宫出口则求解了一种可行的路径；若沿入口的所有方向都不能到达出口，则说明此迷宫不存在可行路径。这种经试探可行则行进，不可行则返回重新试探的方法，则可以作为该问题的求解方法。三、具体实现1.迷宫实现用一个二维数组代表迷宫，数组的值用1或0表示，1表示不通，0表示可通。2.过程实现用一个栈存储探索过程中生成的路径，若当前位置可通时，则将其入栈纳入路径；而当返回前一位置时，则进行出栈操作。四、源代码（一）头文件1、数组位置的定义#includeiostreamusingnamespacestd;typedefstruct//位置类定义{intx;//行下标inty;//列下标}posType;typedefstruct//路径栈中元素定义类型{posTypepos;//路径中的通道位置intdirc;//从前一位置到该位置的行进方向，值1~4分别代表右，下，左，上}SElemType;2、栈的定义，以及栈的相应函数的定义#defineStackSpaceIncr20typedefstruct{SElemType*base;inttop;intstackSize;}SqStack;//栈intInitSqStack(SqStack&S,intInitSize)//初始{S.base=(SElemType*)malloc(InitSize*sizeof(SElemType));if(!S.base)return-2;S.stackSize=InitSize;S.top=0;return1;}boolstackIsEmpty(SqStackS)//判空{if(!S.top)returntrue;elsereturnfalse;}intPush(SqStack&S,SElemTypee)//入栈{SElemType*newbase;if(S.top==S.stackSize){newbase=(SElemType*)realloc(S.base,(S.stackSize+1)*sizeof(SElemType));if(!newbase)return-2;S.base=newbase;S.stackSize+=1;}S.base[S.top]=e;S.top++;return1;}intPop(SqStack&S,SElemType&e)//出栈{if(!S.top)return0;S.top--;e=S.base[S.top];return1;}intgetTop(SqStackS,SElemType&e){if(!S.top)return0;e=S.base[S.top-1];return1;}intstackEmpty(SqStackS){if(!S.top)return1;elsereturn0;}intstackLength(SqStackS){returnS.top;}（二）主函数以及实现#includeStatus.h#includeStack.h#includeiostreamusingnamespacestd;#defineRow12#defineCol12posTypenextPos(posTypecurPos,intd)//返回curPos沿方向d行进的下一位置{posTypepos;switch(d){case1:pos.x=curPos.x;pos.y=curPos.y+1;break;//向右case2:pos.x=curPos.x+1;pos.y=curPos.y;break;//向下case3:pos.x=curPos.x;pos.y=curPos.y-1;break;//向右case4:pos.x=curPos.x-1;pos.y=curPos.y;break;//向上}returnpos;}boolcanGo(posTypepos,intM[Row][Col])//判断pos位置是否可通{if(M[pos.x][pos.y]==0)//为为走过的通道块returntrue;elsereturnfalse;}boolMaze(intM[Row][Col],posTypeend,posTypestart)//对于迷宫问题M，求解从入口到出口的一个路径，存在返回TURE否则返回FALSE{SqStackS;SElemTypee;posTypecurPos;intd,step;InitSqStack(S,100);curPos=start;//当前位置初始为入口位置，并设其来向为最后一个方向4d=4;do{if(canGo(curPos,M))//curPos可通{M[curPos.x][curPos.y]=2;//用2标记次位置，表示corPos“已走过”e.pos=curPos;//当前位置及来向纳入路径栈e.dirc=d;Push(S,e);if(curPos.x==end.x&&curPos.y==end.y)break;//到达出口，结束循环d=1;curPos=nextPos(curPos,d);//下一行进方向为1}elseif(d4)//curpos不可通过且前一位置尚有未探索方向，顺序探索下一方向{d++;getTop(S,e);curPos=nextPos(e.pos,d);}elseif(!stackEmpty(S))//d=4时，出栈后退至前一位置{Pop(S,e);d=e.dirc;curPos=e.pos;}}while(!stackIsEmpty(S));if(!stackEmpty(S))//存在路径{Pop(S,e);M[e.pos.x][e.pos.y]='e';//出口标记为ed=e.dirc;//前一位置的进行方向for(step=stackLength(S);step0;step--)//标记路径上的每个位置{Pop(S,e);switch(d){case1:M[e.pos.x][e.pos.y]=26;break;//-case2:M[e.pos.x][e.pos.y]=25;break;//-case3:M[e.pos.x][e.pos.y]=27;break;case4:M[e.pos.x][e.pos.y]=24;break;}d=e.dirc;}M[start.x][start.y]='s';//入口标记为sreturn1;}elsereturn0;}voidprintMaze(intM[Row][Col],posTypeend,posTypestart)//输出迷宫{inti,j;//printf(迷宫：入口(%d%d),出口(%d%d)\n,start.x,start.y,end.x,end.y);cout迷宫：入口start.x,start.y出口end.x,end.y;coutendl;printf(\t%1c,'');for(i=0;iCol;i++)couti;//printf(%3d,i);coutendl;for(i=0;iRow;i++){printf(\t%2d,i);for(j=0;jCol;j++){if(M[i][j]==1)cout|||;//输出墙体块elseif(M[i][j]==0)cout;//输出为走过的通道块elseif(M[i][j]==2)cout=;//输出探视过单不能到达出口的通道块elseprintf(%c,M[i][j]);//输出路径块，用箭头表示其行进方向}coutendl;}coutendl;}voidmain(){intM[Row][Col]=//定义表示迷宫{{1,1,1,1,1,1,1,1,1,1,1,1},{1,0,0,0,1,1,0,1,1,1,0,1},{1,0,1,0,0,1,0,0,1,0,0,1},{1,0,1,1,0,0,0,0,1,0,1,1},{1,0,0,1,0,1,0,0,0,0,0,1},{1,1,0,1,0,1,1,0,1,0,1,1},{1,0,0,1,0,0,0,0,1,1,1,1},{1,0,1,0,1,1,1,1,0,0,1,1},{1,0,0,0,0,1,1,0,0,0,1,1},{1,0,1,0,1,0,0,0,1,0,0,1},{1,0,0,0,0,0,1,0,0,1,0,1},{1,1,1,1,1,1,1,1,1,1,1,1}};posTypestart,end;start.x=1;start.y=1;//定义入口end.x=10,end.y=10;//定义出口couta;//输出初始迷宫printMaze(M,start,end);if(Maze(M,start,end)){cout找到可行路径endl;printMaze(M,start,end);//输出带有探索标记和路径标记的迷宫}elsecout无可行路径endl;system(pause);}五、演示截图五、小组成员分工蔡聪聪{头文件，栈的定义，posTypenextPos函数（返curPos沿方向d行进的下一位置）何保平{栈基本函数的实现，迷宫的定义，判断是否可通函数的实现，吴俊文{boolMaze(intM[Row][Col],posTypeend,posTypestart)//对于迷宫问题M，求解从入口到出口的一个路径，存在返回TURE否则返回FALSE；