课程设计说明书-数据结构与算法设计综合设计-迷宫的生成与路由.pdf

课程设计说明书课程名 称：数据结构与算法设计综合设计课程代码:_题 目：迷宫的生成与路由年级专业斑:_学生姓名:_学 号:_开始时间:年 月 日完成时间:年 月 日课程设计成绩：指导教师签名：年 月 日平时学习 态度与效果(30)技术水平与 实际能力(30)团队协作与 技术创新(10 分)设计说明书 撰写质量(30)总分(100)目 录1需求分析.12概要设计.33详细设计.94调试分析.205用户使用说明.226测试结果.247 结论.26致谢.29参考文献.30摘要用GH语言编写的生成一个MN行皿U）的迷宫，完成迷宫的组织 和存储，并实现迷宫路由算法。（D使用二维数组mtrixM风表示迷宫,其中MN为迷宫的行、列数，当元素值为0时表示该点是通路，当元素值 为1时表示该点是墙。在每一点都有4种方向可以走，可以用数组wall M 来表示每一个方向上的墙，用另一个二维数组graph M N记录墙和节点的 情况。（2）选用深度优先算法和广度优先算法寻找路径，迷宫由程序自动 创建。关键词：迷宫生成、广度优先、深度优先引言1需求分析设计算法生成一个N*M（N行M歹D的迷宫，并完成迷宫的组织和储存。实 现两种不同的迷宫算法：广度优先，深度优先算法。要求：1.N和M是用户可配置的，缺省值为50和50。2.迷宫的入口和出口分别在第0行和第N-1行上，随机选择。3.生成迷宫要求是随机，且连通的。4.迷宫具有多条分支路线。5.进行深度优先探索迷宫路径并进行输出。6.进行广度优先探索迷宫路径并进行输出。7.实现图形化界面显示。8.在图形界面输出寻路过程坐标。8.实现按钮事件处理的图形用户界面交互。L1任务与分析随机生成一个迷宫（由用户规定其大小）并使用。算法分析迷宫是连通的。使用图形表示，并分别在迷宫的笫一行和最后一行随机选择出口和入口，输出可 通迷宫的最佳路径。任务一：迷宫随机生成算法的实现。任务二：迷宫深度.优先搜索算法实现。任务三：迷宫广度优先搜索算法实现。任务三：进行图形界面的表示。分析：对三大主要功能模块进行三大主类设计，分别为Maze类，DFS类，B FS类,最后使用MFC应用程序进行图形界面的表示。1.2测试数据m,n取默认值50,50m,n取默认值20,20m,n取默认值60,602概要设计（此处说明本课程设计题目的模块划分及各模块的功能介绍和对应的函数名（原型）以及各模块间的层次（调用）关系-以框图描述）（1）本系统所设计的函数见表2.1MazeCell 类函数名称函数原型功能描述MazeCellMazeCell();迷宫格对象初 始化。Maze 类函数名称函数原型功能描述MazeMaze(int m=49,int n二 49)初始化迷宫行数和列数，构造 节点矩阵c reateMazevoid c reateMaze()随机创建课连 通迷宫printMazevoid printMaze()在DOS界面打印 迷宫hasUnac c essAdjNodebool hasUnac c essAdjNode(int,int)判断下一节点 是否可以访问breakWallvoidbreakWall(MazeCell*)拆掉墙，使两节 点连通toNextNodevoid toNextNode()移动当前节点 到下一节点makeR omdanStartAndEndvoid makeR omdanStartAndEndO随机生成入口 和出口getGraphR owint getGraphR ow()返回迷宫矩阵 的行数getGraphColumnint getGraphColumn()返回迷宫矩阵 的列数MazeMaze()销毁迷宫，释放 内存getGraphint*getGraph()返回迷宫的矩 阵数组Coordinate 类函数名称函数原型功能描述CoordinateCoordinate(int,int)Coordinate()对象手动初始 化以及默认初 始化getXint getX();获得坐标X值getYint getY();获得坐标Y值DFS类函数名称函数原型功能描述DFSDFS(int*graph,int,int);DFS对象初始化mazePathvoid mazePath();DFS算法寻找生 成迷宫路径hasPathbool hasPath(int x,int y);有可访问迷宫 格判断printPathvoid printPath();Dos界面打印路径getValueint getValue(int,int);获得DFS对象某 个迷宫格的 value 值B FS类函数名称函数原型功能描述B FSB FS(int*graph,int,int);B FS对象初始化mazePathvoid mazePath();B FS算法寻找生 成迷宫路径hasPathbool hasPath(int x,int y);有可访问迷宫 格判断printPathvoid printPath();Dos界面打印路径getValueint getValue(int,int);获得B FS对象某 个迷宫格的 value 值MFC应用程序函数名称函数原型功能描述OnB nC1ic kedCreatemazeOnB nClic kedCreatemaze()点击“生成迷 宫”按钮随机生 成迷宫，并且在 窗口进行显示OnB nClic kedDfsOnB nClic kedDfs()点击“DFS寻路”按钮在生成迷 宫上进行DFS寻 路，在窗口显示OnB nClic kedB fsOnB nClic kedB fs()点击“B FS寻路”按钮在生成迷 宫上进行B FS寻 路，在窗口显示OnB nClic kedExitOnB nClic kedExit()点击”退出按 钮”，程序关闭 退出OnB nC1ic kedAboutOnB nClic kedAbout()点击“关于”按 钮，显示程序使 用说明及其他(2)本系统函数的调用关系见图2.10按钮：DFS寻路使用DFS类创建一个对象,进行DFS路径寻找按钮：BFS寻路使用BFS类创建一个对象,今夏BFS路径寻找按钮：退出退出并关闭应用程序按钮：关于弹出窗口，显示使用说明等内 容Maze类对象创建构造函数进行初始化，构建节点矩阵和迷、宫矩阵createMaze函数根据节点矩阵进行迷宫的 随机创建，并将生成迷宫保存在迷宫矩阵 _ _/算法阐述：迷宫节点以及相关功能函数定 义规定墙占用格子规定每个节点代表一个可通过 格子，节点有四面墙边框为墙采用深度优先算法生成迷宫if存在可访问节点if存在当前节点可访问的 邻节点随机获得邻节点清空当前结点和邻节点 中间的墙当前结点入栈设置邻节点属性为已访 问邻节点置为当前结点else if若栈不为空令栈顶节点为当前结点 else随机取节点置为当前结点迷宫随机生成完成DFS对象创建 _zDFS对象初始化mazePath。进行DFS寻路，并将结果保存在、矩阵中，算法阐述：.使用graph进行DFS搜索，graph 为二维数组，其中1为墙，0为路while存在未访问迷宫格if存在当前迷宫格可访问 的邻格子当前迷宫格周围（上下左右）存在格子为0if存在向下的格子 当前格子入栈 向下邻格子设为当 前格子访问数+e I se当前格子入栈邻格子设为当前格 子访问数+else if若栈不为空令栈顶格子为当前格子 else随机取格子置为当前格子DFS寻路完成3详细设计（对概要设计部分所介绍的功能模块进行详细介绍及实现。并给出相应函数 的定义即实现函数。）1.节点类型和指针类型MazeCell*matrix 存储迷宫节点的数组sac/risAc c essed=true;初始点为0,0 标记为真Ac c essed+=1;访问节点加1toNextNodeO;寻找下一节点for(int i=0;irow;i+)将每一行节点的上下墙(也有是可 能已经被拆掉成为可走的格子)弄为迷宫里的该节点格子上下格子(for(int j=0;jc olumn;j+)(graph2*i2*j+1=*matrixij.wall;if(i=row-1)(graph2*i+22*j+1=*(matrixi j.wall+1)；for(int j=0;c olumn;j+)将每一列节点的左右墙(也有 可能是可走)弄为迷宫里的该节点格子左右格子(for(int i=0;irow;i+)(graph 2*i+1 2*j=*(matrix i j.wall+2);if(j=c olumn-1)graph2*i+12*j+2=*(matrixi j.wall+3);makeR andomStartAndEnd();随机定义迷宫出入口cout n现在生成迷宫！：x;int c urrentY=c urrentCoordinate-y;mazePointerc urrentXc urrentY.ac c essed=true;mazePointerc urrentXc urrentY.value=2;int i;while(c urrentX!=(m-1)c urrentX=c urrentCoordinate-x;c urrentY=c urrentCoordinate-y;i=T；记录有效相邻格子数c out X:c urrentX Y:“c urrentY ac c essed=true;pathStac k.push(*c urrentCoordinate);将上一个格子坐 标进栈c urrentCoordinate=tempi;c urrentCoordinate-value=2;c urrentCoordinate-ac c essed=true;ac c esseCount+;c urrentX=c urrentCoordinate-x;c urrentY=c urrentCoordinate-y;elseif(!pathStac k.empty()当前格子无可走的相邻格子,返回到上一个格子(mazePointerc urrentXc urrentY.value=-1;c urrentCoordinate=&pathStac k.top();pathStac k.pop();)4.B FS算法实现void B FS:mazePath()(c urrentCoordinate=new CoordinateB FS(0,start);int c ount 1=0,c ount2=0;c ountl为记录前一个被访问格子(栈顶部格子)可走相邻格子数，c ount2为当前访问格子的可走相邻格子数int c urrentX=c urrentCoordinate-x;int c urrentY=c urrentCoordinate-y;mazePointerc urrentXc urrentY.ac c essed=true;mazePointerc urrentXc urrentY.value=2;/int entry=startPoint;入口 id/int exit=endPoint;出口id记录所有房间的访问路径,traPath i 表示访问到房间i的路径上的前 一节点/vec tor traPath(endPoint,-1);/depathQ uery pathQ uery;s_ i=0;s 二 new CStringm*n;pathQ uery.push_ bac k(mazePointer0start);while(!pathQ uery.empty()(if(c urrentX 二二(m-1)break;int i=0;/if(mazePointerc urrentX c urrentY.value=2)如果已 经该房间已经访问过了，则跳过/c ontinue;if(hasPath(c urrentX,c urrentY-1)pathQ uery.push bac k(mazePointerc urrentXc urrentY-1)；/mazePointerc urrentXc urrentY-11.value=2;c urrentCoordinate-ac c essed=true;i+；)if(hasPath(c urrentX,c urrentY+1)(pathQ uery.push_ bac k(mazePointerc urrentXc urrentY+1)；/mazePointerc urrentXc urrentY+1.value=2;c urrentCoordinate-ac c essed=true;i+；if(hasPath(c urrentX-1,c urrentY)(pathQ uery.push bac k(mazePointerc urrentX-1c urrentY);/mazePointerc urrentX-1c urrentY.value=2;c urrentCoordinate-ac c essed=true;i+；if(hasPath(c urrentX+1,c urrentY)(pathQ uery.push_ bac k(mazePointerc urrentX+1c urrentY);/mazePointerc urrentX+1c urrentY.value=2;c urrentCoordinate-ac c essed=true;i+；)if(i 二二 0)mazePointerc urrentXc urrentY.value=-1;elsemazePointerc urrentXc urrentY.value=2;pathQ uery.pop_ front();c urrentCoordinate=fepathQ uery.front();c urrentX=c urrentCoordinate-x;c urrentY=c urrentCoordinate-y;s s_ i+.Format(_ T(，z(%d,%d)nz，),c urrentX,c urrentY);/c out X:c urrentX Y:c urrentY endl;)5.MFC按钮功能实现void CMaze_ MFCDlg:OnB nClic kedCreatemaze()/TODO:在此添加控件通知处理程序代码 int m,n;UpdateData(TR UE);if(m_ MazeX=0|m_ MazeY 二二 0)m=50;n=50;else(m=(int)mMazeX;n=(int)mMazeY;)Maze maze(m,n);创建迷宫对象maze.c reateMaze();r=maze.getGraphR ow();c=maze.getGraphColumn();Arr=maze.getGraph();Arr=new int*maze.getGraphR ow();for(int i=0;imaze.getGraphR ow();i+)Arri=new intmaze.getGraphColumn();for(int i=0;ir;i+)for(int j=0;jc;j+)Arri j=maze.getGraph()ij;/double length=50;/double wide=50;/*int x=5;int y=5;*/HDC hdc=:GetDC(m hWnd);HB R USH hbrush_ B K,hbrush01d_ B K;hbrush B K=CreateSolidB rush(R GB(255,255,255);hbrush01d_ B K=(HB R USH)Selec tObjec t(hdc,hbrush_ B K);:R ec tangle(hdc,0,0,700,700);Selec tObjec t(hdc,hbrush01d_ B K);DeleteObjec t(hbrush_ B K);for(int i=0;i r;i+)(for(int j=0;j c;j+)if(Arrij=1)墙(HB R USH hbrush,hbrushOld;hbrush=CreateSolidB rush(R GB(138,54,15);hbrushOld=(HB R USH)Selec tObjec t(hdc,hbrush);:R ec tangle(hdc,i*10,j*10,i*10+10,j*10+10);Selec tObjec t(hdc,hbrushOld);DeleteObjec t(hbrush);):R eleaseDC(m_ hWnd,hdc);void CMaze_ MFCDlg:OnB nClic kedDfs()/TODO:在此添加控件通知处理程序代码DFS dfs(Arr,r,c);dfs.mazePath();/*dfs.printPath();*/HDC hdc=:GetDC(m hWnd);for(int i=0;i r;i+)(for(int j=0;j c;j+)if(dfs.getValue(i,j)二二 2)(HB R USH hbrush,hbrushOld;hbrush=CreateSolidB rush(R GB(0,0,255);hbrushOld=(HB R USH)Selec tObjec t(hdc,hbrush);:R ec tangle(hdc,i*10,j*10,i*10+10,j*10+10);Selec tObjec t(hdc,hbrushOld);DeleteObjec t(hbrush);else if(dfs.getValue(i,j)二二-1)(HB R USH hbrush_ 2,hbrush01d_ 2;hbrush_ 2=CreateSolidB rush(R GB(125,125,255);hbrush01d_ 2=(HB R USH)Selec tObjec t(hdc,hbrush_ 2);:R ec tangle(hdc,i*10,j*10,i*10+10,j*10+10);Selec tObjec t(hdc,hbrush01d_ 2);DeleteObjec t(hbrush_ 2);):R eleaseDC(m_ hWnd,hdc);m PathCoordinate.R esetContent();for(int i=0;i dfs.s_ i;i+)m PathCoordinate.InsertString(0,dfs.si);)void CMaze_ MFCDlg:OnB nClic kedB fs()/TODO:在此添加控件通知处理程序代码B FS bfs(Arr,r,c);bfs.mazePath();/*dfs.printPath();*/HDC hdc=:GetDC(m hWnd);for(int i=0;i r;i+)(for(int j=0;j c;j+)(if(bfs.getValue(i,j)二二 2)HB R USH hbrush,hbrushOld;hbrush=CreateSolidB rush(R GB(0,0,255);hbrushOld=(HB R USH)Selec tObjec t(hdc,hbrush);:R ec tangle(hdc,i*10,j*10,i*10+10,j*10+10);Selec tObjec t(hdc,hbrushOld);DeleteObjec t(hbrush);else if(bfs.getValue(i,j)=-1)HB R USH hbrush_ 2,hbrush01d_ 2;hbrush_ 2=CreateSolidB rush(R GB(125,125,255);hbrush01d_ 2=(HB R USH)Selec tObjec t(hdc,hbrush_ 2);:R ec tangle(hdc,i*10,j*10,i*10+10,j*10+10);Selec tObjec t(hdc,hbrush01d_ 2);DeleteObjec t(hbrush_ 2);:R eleaseDC(m_ hWnd,hdc);m PathCoordinate.R esetContent();for(int i=0;i LoadIc on(IDR _ MAINFR AME);void CMaze_ MFCDlg:DoDataExc hange(CDataExc hange*pDX)(CDialogEx:DoDataExc hange(pDX);DDX_ Text(pDX,IDC R ow,m MazeX);DDX Text(pDX,IDC_ Column,m_ MazeY);DDX_ Control(pDX,IDC_ LIST,m_ PathCoordinate);B EGIN_ MESSAGE_ MAP(CMaze_ MFCDlg,CDialogEx)0N_ WM_ SYSC0MMAND()0N_ WM_ PAINT()0N_ WM_ Q UER YDR AGIC0N()0N_ B N_ CLICKED(IDC_ CreateMaze,&CMaze_ MFCDlg:OnB nClic kedCreatemaze)ON_ B N_ CLICKED(IDC_ DFS,&CMaze_ MFCDlg:OnB nClic kedDfs)ON_ B N_ CLICKED(IDC_ B FS,&CMaze_ MFCDlg:OnB nClic kedB fs)ON_ B N_ CLICKED(IDC_ EXIT,&CMaze_ MFCDlg:OnB nClic kedExit)ON_ B N_ CLICKED(IDC_ About,&CMaze_ MFCDlg:OnB nClic kedAbout)END_ MESSAGE_ MAP()/CMaze_ MFCDlg消息处埋程序B OOL CMaze_ MFCDlg:0nInitDialog()CDialogEx:OnlnitDialog();/将”关于.”菜单项添加到系统菜单中。/IDM_ AB OUTB OX必须在系统命令范围内。ASSER T(IDM_ AB OUTB OX&OxFFFO)二二 IDM_ AB OUTB OX);ASSER T(IDM_ AB OUTB OX AppendMenu(MF SEPAR ATOR);pSysMenu-AppendMenu(MF_ STR ING,IDM_ AB OUTB OX,strAboutMenu);)/设置此对话框的图标。当应用程序主窗口不是对话框时，框架将自 动/执行此操作Setlc on(m hlc on,TR UE);/设置大图标Setic on(m_ hlc on,FALSE);/设置小图标/TODO:在此添加额外的初始化代码return TR UE;/除非将焦点设置到控件，否则返回TR UEvoid CMaze_ MFCDlg:OnSysCommand(UINT nID,LPAR AM 1Param)(if(nID&OxFFFO)=IDM_ AB OUTB OX)CAboutDlg dlgAbout;dlgAbout.DoModai();)elseCDialogEx:OnSysCommand(nID,1Param);)/如果向对话框添加最小化按钮，则需要下面的代码/来绘制该图标。对于使用文档/视图模型的MFC/这将由框架自动完成。void CMaze_ MFCDlg:0nPaint()if(Islc onic()CPaintDC de(this);/用于绘制的设备上下文SendMessage(WM_ ICONER ASEB KGND,reinterpret_ c ast(de.GetSafeHdc(),0);/使图标在工作区矩形中居中int c xlc on=GetSystemMetric s(SM_ CXICON);int c ylc on=GetSystemMetric s(SM_ CYIC0N);CR ec t rec t;GetClientR ec t(&rec t);int x 二(rec t.Width()-c xlc on+1)/2;int y 二(rec t.Height()-c ylc on+1)/2;/绘制图标de.Drawic on(x,y,m_ hlc on);)else(CDialogEx:OnPaint();当用户拖动最小化窗口时系统调用此函数取得光标 显小。HCUR SOR CMaze_ MFCDlg:OnQ ueryDragIc on()return static _ c ast(m hlc on);3.2 数据录入实现应用程序,m,n取默认值50,50m,n取默认值20,20m,n取默认值60,604调试分析（该部分内容包括：对准备进行测试的数据进行测试，并对在调试过程中遇到的问题是如 何分析和解决的进行描述。）1.问题1：数组越界问题描述：寻路过程，发生越界的情况问题解决：搜寻路径是添加越界检查函数2.问题2：死循环问题描述：迷宫创建过程，发生死循环情况问题解决：添加判断语句判断当前节点是否已到达终点3.问题3：坐标问题问题描述：只能输出一个坐标问题解决：使用CString数组存储所有节点的坐标，最后输出5用户使用说明此处说明如何使用你所设计的软件1.输入X和Y的值，点击生成迷宫进行随机生成，可重复点击，随机生成。2.如未输入X和Y的值，则默认值为50,点击生成迷宫按钮，随机生成迷 宫，可重复生成。3.生成迷宫之后，点击DFS寻路，会生成DFS路径，寻路坐标表示在右边 空栏。4.生成迷宫之后，点击B FS寻路，会生成B FS路径，寻路坐标表示在右边 空栏。5.点击退出按钮，程序会关闭退出6.点击相关按钮，会提示应用程序使用说明。6测试结果（此处应对你所设计的软件和经过测试，下个结论。分别使用默认值（50,50）输入值（20,20）（60,60）进行迷宫生成，DFS寻路，B FS寻路 测试，测试结果如下：X个迷宫的生成与路由迷宫横长：迷宫纵长I50 I M 一DFS寻路BFS寻路退出关于X(48,43)(46,43)(16,47)(11,46)(14,35)(25,32)(32,39)(16,47)(11,46)(14,35)(25,32)(32,39)(47,22)(47,22)(43,39)(45,41)(47,43)(15,47)(11,47)(15,35)A迷宫的生成与路由生成迷宫迷宫横长：迷宫纵长宦关于XJ*J*)x/7)z/*-*.*-J*1/JZ x)z 3211111234555677 J*77l/X 乙乙乙工工工工工71 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 9 9 Q-9 C z(x z(*z(z(z(x/(X z(z(z(z(z(x z(/V#(x z(/k z(zrlx/(zfXJ*)z XI/)J,)JZ V)*XI/7 J*J/)/J JZ u 333211111234555677)乙乙乙6,1/-7为工工工工工 z LLba,7,6二 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Q-Q-n/)J*XJ-J J*17 17 J yj,JX JZ XJ#XJ 99901112345677789990122233333333333333334 乙伉 乙 乙 zulrrlrrlH乙乙755555555555555555555c zl/k/k#(x zk zr z(x/(x#(x z(ZK*zf/k fx/I fk z(x(X#(/X(58,29)(57,28)(57,46)(13,33)(47,51)(57,29)(57,45)(57,29)(57,45)(47,51)(57,29)(57,45)(57,29)(57,45)(13,33)(47,51)(57,29)(57,45)(57,29)(57,45)迷宫横长：迷宫纵长160 160生成迷宫DFS寻路 BFS寻路退出关于迷宫纵殳UlZtj,)1/xlz 3333333211111O999876C 444444444444443333330(4(4(4l*1 宫横长:生成迷宫DFS寻路BFS寻路退出迷喜的生成与路由：本程序使用迷宫三大生成算法之一深度优先随机生成迷宫算法，使用说 明如下1.输入X和Y的值，点击生成迷宫进行随机生成，可重复点击，随机生成。2.如未输入X和Y的值，则默认值为50，点击生成迷宫按钮，随机生成迷宫，可重复生成。3.生成迷宫之后，点击DFS寻路，会生成DFS路径，寻路坐标表示在右边空栏。4.生成迷宫之后，点击BFS寻路，会生成BFS路径，寻路坐标表示在右边空栏。5.点击退出按钮，程序会关闭退出6.点击相关按钮，会提示应用程序使用说明。关于结论通过本次课程设计可以得出结论如下：1.迷宫深度优先算法可以迅速生成一个矩形迷宫，但是生成迷宫具有一条 明显的通路。2.迷宫DFS路径探索，可以明显在使用较少计算量的情况下的寻求一条迷 宫通路。3.迷宫B FS路径探索，需要进行大量的计算，其速度不如DFS路径探索但 可以找到具有最优解的路径。4.通过本次课程设计，深入探索了栈，队列等数据结构的应用，以及深刻 学习了 DFS算法和B FS算法在实际中的应用，并且对于程序编写能力进 行了显著锻炼。致谢本次课程设计能够得到这样的成果，感谢指导老师的倾力执导，以及各位组员 的辛勤努力。7附录程序源代码：B FS.httpragma onc e ttinc lude#inc lude/zMaze.h#inc lude using namespac e std;c lass CoordinateB FS(friend c lass B FS;public:CoordinateB FS()(x=y=value=0;ac c essed=false;CoordinateB FS(int a,int b)(x=a;y=b;value=0;ac c essed=false;int getX();int getY();int x;int y;int value;bool ac c essed;)；c lass B FS/TODOpublic:CString*s;int s_ i;B FS(int*graph,int graphR ow,int graphColumn);B FS();/void getMaze(int*,int,int);void mazePath();bool hasPath(int x,int y);void printPath();int getValue(int,int);private:Coordinatc B FS*mazePointer;int m;int n;int start;int end;deque pathQ uery;int ac c esseCount;CoordinateB FS*c urrentCoordinate;);B FS.c ppttinc lude stdafx.h#inc lude B FS.hint CoordinateB FS:getX()(return x;int CoordinateB FS:getY()(return y;B FS:B FS(int*graph,int graphR ow,int graphColumn)mgraphR ow;n=graphColumn;ac c esseCount=1;mazePointer=new CoordinateB FS*graphR ow;for(int i=0;igraphR ow;i+)(mazePointeri=new CoordinateB FSgraphColumn;)for(int i=0;i graphR ow;i+)for(int j=0;j graphColumn;j+)mazePointerij.value=graphij;mazePointeri j.x=i;mazePointeri j.y=j;mazePointerij.ac c essed=false;/*for(int k=0;k 3;k+)mazePointerij.hasWayk=0;*/for(int i=0;i n;i+)if(mazePointer0i.value=0)start=i;for(int i=0;i n;i+)if(mazePointerm-1 i.value=0)end=ic out testfor(int i=0;i m;i+)(for(int j=0;j n;j+)(if(mazePointerij.value=0)(c out mazePointerij.value;c out mazePointerij.x mazePointerij.y c out endl;c out testover-B FS:广B FS()for(int i=0;im;i+)delete mazePointeri;delete1 mazePointer;delete s;bool B FS:hasPath(int x,int y)(越界检测if(xm-1)return false;if(yn-1)return false;访问检测if(mazePointerxy.ac c essed)return false;if(mazePointerxy.value!=0)return false;return true;/c ur=startc ur入队/while(队不空)(if(到达出口)/break如果c ur已访问/c ontinueif(有可访问邻点)该邻点入队设置该邻点已访问/c ur=front/front 出队void B FS:mazePath()c urrentCoordinate=new CoordinateB FS(0,start);int c ount 1=0,c ount2=0;c ountl为记录前一个被访问格子(栈顶部格子)可走相邻格子 数，c ount2为当前访问格子的可走相邻格子数int c urrentX=c urrentCoordinate-x;int c urrentY=c urrentCoordinate-y;mazePointerc urrentXc urrentY.ac c essed=true;mazePointerc urrentXc urrentY.value=2;/int entry=startPoint;入口id/int exit=endPoint;出口 id记录所有房间的访问路径,traPathi表示访问到房间i的路径上的前一节点/vec tor traPath(endPoint,-1);/depathQ uery pathQ uery;s_ i=0;s=new CStringm*n;pathQ uery.push_ bac k(mazePointer0start);while(!pathQ uery.empty()(if(c urrentX=(m-1)break;int i=0;/if(mazePointerc urrentX c urrentY.value=2)如果已经该房间已经访问过了，则跳过/c ontinue;if(hasPath(c urrentX,c urrentY-1)(pathQ uery.push bac k(mazePointerc urrentXc urrentY-11);/mazePointerc urrentXc urrentY-1.value=2;c urrentCoordinate-ac c essed=true;i+；if(hasPath(c urrentX,c urrentY+1)(pathQ uery.push_ bac k(mazePointerc urrentXc