迷宫问题课程设计报告

1、精选优质文档-倾情为你奉上课程设计报告课程设计题目：小组成员 何保平（8）蔡聪聪（9）吴俊文（0）班 级 专 业 软件工程指导教师 高永平 2016年01月 05日一、任务可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出。二、问题分析 迷宫问题采用试探法求解，即从入口出发，在当前位置任选一个方向向前试探，若下一位置可通（即该位置为从未走过的通道块）则继续试探行进；若当前位置的所有方向均不通（为墙体或已走过的通道块）时，则按原路返回上一位置，重新选择其他方向继续试探前进。这样不断试探前进，知道到达迷宫出口则求解了一种可行的路径；若沿入口的所有方向都不能到达出口，

2、则说明此迷宫不存在可行路径。这种经试探可行则行进，不可行则返回重新试探的方法，则可以作为该问题的求解方法。三、具体实现1.迷宫实现用一个二维数组代表迷宫，数组的值用1或0表示，1表示不通，0表示可通。2.过程实现用一个栈存储探索过程中生成的路径，若当前位置可通时，则将其入栈纳入路径；而当返回前一位置时，则进行出栈操作。四、源代码（一）头文件1、数组位置的定义#include<iostream>using namespace std;typedef struct /位置类定义int x; /行下标int y;/列下标 posType;typedef struct /路径栈中元素定义类

3、型posType pos;/路径中的通道位置int dirc;/从前一位置到该位置的行进方向，值14分别代表右，下，左，上SElemType;2、栈的定义，以及栈的相应函数的定义#define StackSpaceIncr 20typedef struct SElemType *base;int top;int stackSize;SqStack; /栈int InitSqStack(SqStack&S,int InitSize) /初始S.base=(SElemType*)malloc( InitSize* sizeof (SElemType);if(!S.base)return -

4、2;S.stackSize=InitSize;S.top=0;return 1;bool stackIsEmpty(SqStack S) /判空if(!S.top)return true;else return false;int Push(SqStack&S,SElemType e)/入栈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.

5、stackSize+=1;S.baseS.top=e;S.top+;return 1;int Pop(SqStack&S,SElemType&e)/出栈if(!S.top) return 0;S.top-;e=S.baseS.top;return 1;int getTop(SqStack S,SElemType&e)if(!S.top) return 0;e=S.baseS.top-1;return 1;int stackEmpty(SqStack S)if(!S.top) return 1;else return 0;int stackLength(SqStack S

6、)return S.top;（二）主函数以及实现#include"Status.h"#include"Stack.h"#include<iostream>using namespace std;# define Row 12# define Col 12posType nextPos(posType curPos,int d)/返回curPos沿方向d行进的下一位置posType pos;switch(d)case 1: pos.x=curPos.x;pos.y=curPos.y+1;break; /向右 case 2: pos.x=curP

7、os.x+1;pos.y=curPos.y;break; /向下case 3: pos.x=curPos.x;pos.y=curPos.y-1;break; /向右case 4: pos.x=curPos.x-1;pos.y=curPos.y;break; /向上return pos;bool canGo(posType pos,int MRowCol)/判断pos位置是否可通if(Mpos.xpos.y=0)/为为走过的通道块return true;else return false;bool Maze(int MRowCol,posType end,posType start)/对于迷宫问

8、题M，求解从入口到出口的一个路径，存在返回TURE 否则返回FALSESqStack S;SElemType e;posType curPos;int d,step;InitSqStack(S,100);curPos=start;/当前位置初始为入口位置，并设其来向为最后一个方向4d=4;doif(canGo(curPos,M)/curPos可通McurPos.xcurPos.y=2;/用2标记次位置，表示corPos“已走过”e.pos=curPos;/当前位置及来向纳入路径栈e.dirc=d;Push(S,e);if(curPos.x=end.x&&curPos.y=end

9、.y) break;/到达出口，结束循环d=1;curPos=nextPos(curPos,d);/下一行进方向为1else if(d<4)/curpos不可通过且前一位置尚有未探索方向，顺序探索下一方向d+;getTop(S,e);curPos=nextPos(e.pos,d);else if(!stackEmpty(S)/d=4时，出栈后退至前一位置Pop(S,e);d=e.dirc;curPos=e.pos;while(!stackIsEmpty(S);if(!stackEmpty(S)/存在路径Pop(S,e);Me.pos.xe.pos.y='e'/出口标记为e

10、d=e.dirc;/前一位置的进行方向for(step=stackLength(S);step>0;step-)/标记路径上的每个位置Pop(S,e);switch(d)case 1:Me.pos.xe.pos.y=26;break;/->case 2:Me.pos.xe.pos.y=25;break;/<-case 3:Me.pos.xe.pos.y=27;break;case 4:Me.pos.xe.pos.y=24;break;d=e.dirc;Mstart.xstart.y='s'/入口标记为sreturn 1;else return 0;void p

11、rintMaze(int MRowCol,posType end,posType start)/输出迷宫int i,j;/printf("迷宫：入口(%d%d),出口(%d%d)n",start.x,start.y,end.x,end.y);cout<<"迷宫：入口<"<<start.x<<","<<start.y<<">出口<" <<end.x<<","<<end.y<<

12、;">"cout<<endl;printf("t%1c",' ');for(i=0;i<Col;i+)cout<<" "<<i;/printf("%3d",i);cout<<endl;for(i=0;i<Row;i+)printf("t%2d",i);for(j=0;j<Col;j+)if(Mij=1) cout<<"|"/输出墙体块else if(Mij=0) cout<

13、;<" "/输出为走过的通道块else if(Mij=2) cout<<" = "/输出探视过单不能到达出口的通道块else printf(" %c ",Mij);/输出路径块，用箭头表示其行进方向cout<<endl;cout<<endl;void main()int MRowCol=/定义表示迷宫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,

14、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;posType start,end;start.x=1;start.y=1;/定义入口end.x=10,end.y=10;/定义出口cout<<"a"/输出初始迷宫printMaze(M,start,end);if(Maze(M,start,end)cout<<"找到可行路径"<<endl;printMaze(M,start,end);/输出带有探索标记和路径标记的迷宫else cout<<"无可行路径"<&