迷宫问题课程设计论文

存档资料成绩：华东交通大学理工学院课程设计报告书所属课程名称数据结构课程设计题目深度与广度搜索：迷宫问题分院专业班级计算机科学与技术2班学号学生姓名指导教师2014年6月17日华东交通大学理工学院课程设计报告第34页共34页序号项目等级优秀良好中等及格不及格1课程设计态度评价2出勤情况评价3任务难度评价4工作量饱满评价5任务难度评价6设计中创新性评价7论文书写规范化评价8综合应用能力评价综合评定等级课程设计（论文）评阅意见评阅人职称20年月日

目录TOC\o"1-3"\h\u6494第一章课程设计内容及要求 4161531.1设计内容 419921.2设计要求 419405第二章总体设计 56292.1.环境设置 5326422.2.图形界面设计 5270642.3.设计思路 631152第三章功能实现 7179023.1.主窗口及消息窗口的实现 7299423.2．文件流的实现 8215103.3．构造迷宫 8153783.4．深度及广度搜索寻径 922312第四章测试 1090584.1将A*B的矩阵墙拆成迷宫 10247534.2进行深度优先搜索 1049894.3进行广度优先搜索 1122654.4漏洞分析 1221942第五章算法分析 1396625.1时间复杂度分析 1365245.2空间复杂度分析 1315280第六章课程设计心得 158694参考文献 1630959附录（源程序） 1717745致谢 34课程设计内容及要求1.1设计内容 课程设计将要设计并实现一个基于深度优先遍历和广度优先遍历的迷宫程序，程序均由c/c++代码实现，能够自动寻迷宫的终点，并由图形界面演示，图形界面的制作基于win32编程实现。1.2设计要求 1.本设计程序需要拥有图形界面 2.分别以深度优先遍历及广度优先遍历方法进行寻找迷宫终点的演示 3.建立每个单元格四面墙的X*Y位迷宫程序 4.通过随机种子随机拆墙，因此进行两种遍历所发生的路径也是不一样的 5.拥有动态的演示效果，可以观测到深度和广度优先遍历的不同寻径方向和不同的寻径方法第二章总体设计2.1.环境设置操作系统：windows7sp1专业版，windows8专业版，windowsxpsp3程序设计语言：c/c++开发工具：编译：visualc++6.0编码：notepad++6.6.14：外部接口：win32API，因此需要借助Microsoftvisualc++的环境进行编译实现2.2.图形界面设计1：本程序设计采用的是基于windows32API的图形化接口建立的两种类型的图形界面。包括winMain函数的主窗口界面以及MessageBox消息界面。所有程序均基于c++语言。2：图形界面演示。消息窗口（2）主窗口2.3.设计思路程序设计框图如下：MMessagebox_1BFSNewWinMainMessagebox_4WinMainMessagebox_2Messagebox_3DFSOverFileString（注：Messagebox是消息框，分别表示标题栏和开始拆墙和开始深度优先搜索和广度优先搜索。WinMain为主窗口，承载拆墙及各种遍历的实现。NewWinMain为拆墙后的主窗口。）第三章功能实现3.1.主窗口及消息窗口的实现（1）窗口函数LRESULTCALLBACKWndProc(HWND,UINT,WPARAM,LPARAM);（2）WinMain函数intWINAPIWinMain(HINSTANCEhInstance,HINSTANCEhPrevInstance,PSTRszCmdLine,intiCmdShow){};(3)注册窗口iScreenWide=GetSystemMetrics(SM_CXFULLSCREEN);//获取分辨率及置于中间hwnd=CreateWindow(AppName,//窗口类名"深度、广度优先搜索迷宫",//窗口实例的标题名WS_MINIMIZEBOX|WS_SYSMENU,//窗口的风格iScreenWide/2-W*CELL/2,//窗口左上角横坐标(X)CELL,//窗口左上角纵坐标(Y)(W+0.3)*CELL,//窗口的宽，而不是客户区的宽(H+1.2)*CELL,//窗口的高，而不是客户区的高NULL,//窗口无父窗口NULL,//窗口无主菜单hInstance,//创建此窗口的应用程序的当前句柄NULL//不使用该值);（4）消息窗口MessageBox(NULL,TEXT("主程序:彭俊威"),TEXT("数据结构课程设计"),MB_ICONINFORMATION);MessageBox(NULL,TEXT("开始深度优先搜索"),TEXT("搜索方式"),NULL);MessageBox(NULL,TEXT("开始广度优先搜索"),TEXT("搜索方式"),NULL);3.2．文件流的实现(1)将拆墙数据存储在txt文本中，以便下次使用时不必再拆墙。std::ifstreamf("d:\\迷宫拆墙数据.txt");f>>col>>row;f.close();WriteDocument(mazeedge,wall,i);(2)读取文件流std::ifstreamf("d:\\迷宫拆墙数据.txt");f>>col>>row;//从txt文件中获取原来迷宫的规模f.close();std::ifstreamf1("d:\\每个单元格四面墙的数据.txt");for(i=0;i<col*row;i++)f1>>wall[i].wall_l>>wall[i].wall_t>>wall[i].wall_r>>wall[i].wall_b;f1.close();3.3．构造迷宫（1）构造AXB的矩阵。本程序使用的是15X15的矩阵，即总共有255个格子。constintCELL=25;//单元像素宽constintW=15;//迷宫宽度constintH=15;//迷宫高度structPOSITION//每一个单元格的左上坐标{ intx;//单元格横坐标(单位pixel) inty;//单元格纵坐标 intindex_x;//单元格横标 intindex_y;//单元格纵标};（2）拆除单独存在的格子，产生通路DrawPath(hdc,W,H){…MessageBox(NULL,TEXT("现在开始拆墙"),TEXT("消息"),NULL);srand(time(NULL));//系统时间作随机种子x=rand()%col;//随机产生起始点y=rand()%row;Stack.push(position[y*col+x]);//迷宫入口进栈visited[y*col+x]=true;//标记已经访问过while(!Stack.empty())};voidReplace(HDChdc,intx,inty,intz,intk){ HPENhpen; hpen=CreatePen(PS_SOLID,1,RGB(255,255,255)); SelectObject(hdc,hpen);MoveToEx(hdc,x,y,NULL);LineTo(hdc,z,k); DeleteObject(hpen);…};3.4．深度及广度搜索寻径(1)深度搜索寻径，使用栈存储voidDFS(HDChdc){};Stack.push(position[entrance]);//迷宫入口进栈 visited[entrance]=true;Stack.pop();//回溯(2)广度搜索寻径，使用队列存储voidBFS(HDChdc){};Queue.push(position[entrance]);//迷宫入口进队列 visited[entrance]=true;Stack.pop();//回溯测试4.1将A*B的矩阵墙拆成迷宫4.2进行深度优先搜索在未搜索到的情况下进行回溯，从进入此条路径的分叉口选择另一条路。4.3进行广度优先搜索第一步搜索完成后会进行清屏。4.4漏洞分析在windowsxp的环境下会偶尔出现不能清屏的问题，那是因为windowsxp系统默认内存，而当PC的实际内存低于默认内存时会产生内存不足的问题，导致图形载入出问题，但是在清除历史数据之后就不会出问题了。算法分析5.1时间复杂度分析由于该图采用邻接矩阵存储，整个算法遍历的过程所花费的时间复杂度为该矩阵的N(row*col)。而由于其需要分别访问已经定位，需要进行分别2次操作，如下：visited=newbool[col*row];//访问标记for(i=0;i<row;i++)for(j=0;j<col;j++)visited[i*col+j]=false;//初始为未访问状态position=newPOSITION[col*row];for(i=0;i<row;i++)//给每个点定位for(j=0;j<col;j++) { position[i*col+j].x=j*CELL; position[i*col+j].y=i*CELL; position[i*col+j].index_x=j; position[i*col+j].index_y=i; }因此在遍历的时候所需要的时间复杂度为N（2*row*col）。由于深度优先搜索和广度优先搜索都是采用同样的存储方式，并且都是遍历搜索，因此时间复杂度相同，都是N（2*row*col）。（注：row,col分别表示迷宫的行和列）。5.2空间复杂度分析5.2.1深度优先搜索空间复杂度分析当进行深度优先搜索时，所遍历的最短路径即为单一路径，因此最好的空间复杂度是N（row+col），而最坏情况为N（row*col），即通过了最大的回溯之后才找到终点路径。5.2.2广度优先搜索空间复杂度分析当进行广度优先搜索的时候，路径经过所有可能的路径，即最大为row*col，因此，空间复杂度为N（row*col）。课程设计心得终于算是完成了课程设计的全部内容，内心百感交集，本来以为课程设计的内容是很简单的，因为不急不忙的慢慢写着，到同学们都要交的时候我才发现自己还没有做完，顿时觉得是自己出了问题。然后，慢慢的开始在网络上寻找资料，询问前辈的经验和知识，通过同学们和老师的帮助，在自己的努力下，很快的完成了设计内容，并做出了分析报告，感谢老师的认同与朋友们的关系，一起努力。参考文献[1]杨厚群.数据结构（C语言描述）[M].上海：上海交通大学出版社，2013年1月[2]程杰.大话数据结构[M]北京：清华大学出版社2011年6月[3]ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,CliffordStein.算法导论(原书第3版)[M]北京：机械工业出版社2013年7月[4]RobertSedgewick.算法：C语言实现(第1～4部分)基础知识、数据结构、排序及搜索（原书第3版）[M]北京：机械工业出版社2009年10月附录（源程序）#include<windows.h>#include<iostream>#include<ctime>#include<stdlib.h>#include<fstream>#include<stack>#include<queue>constintCELL=25;//单元像素宽constintW=15;//迷宫宽度constintH=15;//迷宫高度structPOSITION//每一个单元格的左上坐标{ intx;//单元格横坐标(单位pixel) inty;//单元格纵坐标 intindex_x;//单元格横标 intindex_y;//单元格纵标};structMazeEdge//储存的是原来迷宫所拆的墙，下次生成迷宫和原来一样拆{ intx; inty; intz; intw;};structWall{ intwall_r;//右墙数据 intwall_l;//左墙数据 intwall_t;//上墙数据 intwall_b;//下墙数据};LRESULTCALLBACKWndProc(HWND,UINT,WPARAM,LPARAM);//窗口函数voidDrawWhiteGround(HDChdc);//将整个客户区绘制为白色voidDrawRedBlock(HDChdc,intl,intt,intr,intb);//绘制迷宫起始点与终止点voidDrawRect(HDChdc,intl,intt,intr,intb);//绘制单元方格voidDrawCell(HDChdc,intl,intt,intr,intb);//绘制移动方块voidDrawGamePlace(HDChdc,intcol,introw);//在客户区绘满单元格voidDrawPath(HDChdc,intw,inth);//迷宫拆墙boolAdj(intx,inty,bool*visited,intcol);//判断该单元格是否有没有被访问的相邻单元格boolAdj_NoWall(intx,inty,bool*visited,Wall*wall,intcol);//判断该单元格是否有没有被访问的相邻单元格并且周围没有墙可以访问voidReplace(HDChdc,intx,inty,intz,intk);//拆墙(用白色划线替换红色划线)voidWriteDocument(MazeEdge*mazeedge,Wall*wall,inti);//将迷宫拆墙数据写入txt文件中boolReadDocument(HDChdc);//从txt文件中读取迷宫拆墙数据voidDFS(HDChdc);//深度优先搜索寻找迷宫路径voidBFS(HDChdc);//广度优先搜索寻找迷宫路径//intWINAPIWinMain(HINSTANCEhInstance,HINSTANCEhPrevInstance,PSTRszCmdLine,intiCmdShow){staticcharAppName[]="ToyBrick";//窗口类名HWNDhwnd;MSGmsg;//消息结构WNDCLASSEXwndclass;//窗口类intiScreenWide;//定义一个整型变量来取得窗口的宽度wndclass.cbSize=sizeof(wndclass);wndclass.style=CS_HREDRAW|CS_VREDRAW;//窗口类型wndclass.lpfnWndProc=WndProc;//窗口处理函数为WndProcwndclass.cbClsExtra=0;//窗口类无扩展wndclass.cbWndExtra=0;//窗口实例无扩展wndclass.hInstance=hInstance;//当前实例句柄wndclass.hIcon=LoadIcon(NULL,IDI_APPLICATION);//默认图标wndclass.hCursor=LoadCursor(NULL,IDC_ARROW);//箭头光标wndclass.hbrBackground=(HBRUSH)GetStockObject(WHITE_BRUSH);//背景为黑色wndclass.lpszMenuName=NULL;//窗口中无菜单wndclass.lpszClassName=AppName;//类名为"ToyBrick"wndclass.hIconSm=LoadIcon(NULL,IDI_INFORMATION);//窗口类的注册if(!RegisterClassEx(&wndclass))//如果注册失败则发出警报声音，返回FALSE{MessageBeep(0);returnFALSE;}//获取显示器分辨率的X值iScreenWide，将程序窗口置于屏幕中央iScreenWide=GetSystemMetrics(SM_CXFULLSCREEN);hwnd=CreateWindow(AppName,//窗口类名"深度、广度优先搜索迷宫",//窗口实例的标题名WS_MINIMIZEBOX|WS_SYSMENU,//窗口的风格iScreenWide/2-W*CELL/2,//窗口左上角横坐标(X)CELL,//窗口左上角纵坐标(Y)(W+0.3)*CELL,//窗口的宽，而不是客户区的宽(H+1.2)*CELL,//窗口的高，而不是客户区的高NULL,//窗口无父窗口NULL,//窗口无主菜单hInstance,//创建此窗口的应用程序的当前句柄NULL//不使用该值);if(!hwnd)returnFALSE;MessageBox(NULL,TEXT("主程序:彭俊威"),TEXT("数据结构课程设计"),MB_ICONINFORMATION);//显示窗口ShowWindow(hwnd,iCmdShow);//绘制客户区UpdateWindow(hwnd);//消息循环while(GetMessage(&msg,NULL,0,0)){TranslateMessage(&msg);DispatchMessage(&msg);}//消息循环结束即程序终止时将消息返回系统returnmsg.wParam;}//窗口过程函数WndProcLRESULTCALLBACKWndProc(HWNDhwnd,UINTiMsg,WPARAMwParam,LPARAMlParam){HDChdc;PAINTSTRUCTps;//charBuffer[20];switch(iMsg){//WM_PAINT(窗口第一次生成时执行,WM_PAINT将图从内存拷到屏幕上)caseWM_PAINT:hdc=BeginPaint(hwnd,&ps);//获得设备环境句柄DrawGamePlace(hdc,W,H);//在客户区绘满单元格if(!ReadDocument(hdc))DrawPath(hdc,W,H);//拆墙MessageBox(NULL,TEXT("开始深度优先搜索"),TEXT("搜索方式"),NULL);DFS(hdc);//深度优先搜索寻找迷宫出口DrawWhiteGround(hdc);//将客户区还原为白色背景ReadDocument(hdc);//重新绘制迷宫MessageBox(NULL,TEXT("开始广度优先搜索"),TEXT("搜索方式"),NULL);BFS(hdc);//广度优先搜索寻找迷宫出口EndPaint(hwnd,&ps);return0;//WM_DESTROY(响应关闭窗口动作)caseWM_DESTROY:PostQuitMessage(0);return0;}returnDefWindowProc(hwnd,iMsg,wParam,lParam);}////////////////////////////////////////////////////////////将整个客户区绘制为白色voidDrawWhiteGround(HDChdc){intcol,row;std::ifstreamf("d:\\迷宫拆墙数据.txt");f>>col>>row;f.close();HBRUSHhbrush=CreateSolidBrush(RGB(255,255,255));SelectObject(hdc,hbrush);Rectangle(hdc,0,0,col*CELL,row*CELL);DeleteObject(hbrush);}//绘制迷宫起始点与终止点voidDrawRedBlock(HDChdc,intl,intt,intr,intb){HBRUSHhbrush=CreateSolidBrush(RGB(255,0,0));SelectObject(hdc,hbrush);Rectangle(hdc,l,t,r,b);DeleteObject(hbrush);}//拆墙(用白色划线替换红色划线)voidReplace(HDChdc,intx,inty,intz,intk){ HPENhpen; hpen=CreatePen(PS_SOLID,1,RGB(255,255,255)); SelectObject(hdc,hpen);MoveToEx(hdc,x,y,NULL);LineTo(hdc,z,k); DeleteObject(hpen);}//画单元格，后面四个参数依次为左上坐标和右下坐标voidDrawRect(HDChdc,intl,intt,intr,intb){MoveToEx(hdc,l,t,NULL);//将起始点移动到(l,t)LineTo(hdc,r,t);LineTo(hdc,r,b);LineTo(hdc,l,b);LineTo(hdc,l,t);}//用绿色画刷画移动目标voidDrawCell(HDChdc,intl,intt,intr,intb){HBRUSHhbrush;hbrush=CreateSolidBrush(RGB(0,255,0));//绿色画刷SelectObject(hdc,hbrush);Rectangle(hdc,l,t,r,b);DeleteObject(hbrush);}//在客户区绘满单元格voidDrawGamePlace(HDChdc,intcol,introw){inti,j;HPENhpen1;hpen1=CreatePen(PS_SOLID,1,RGB(255,0,0));//绘制游戏区域方格线(红色)SelectObject(hdc,hpen1);for(i=0;i<row;i++)for(j=0;j<col;j++)DrawRect(hdc,j*CELL,i*CELL,(j+1)*CELL,(i+1)*CELL);DeleteObject(hpen1);}//迷宫拆墙voidDrawPath(HDChdc,intcol,introw){ intx,y,temp,i(-1); bool*visited;//访问标记 POSITION*position;//储存每个单元格的坐标 POSITIONw; std::stack<POSITION>Stack; MazeEdge*mazeedge; Wall*wall;//储存每个单元格的墙的情况 wall=newWall[col*row];//申请col*row个单元格for(x=0;x<row;x++)//请所有单元格的四面墙初始化为都有状态 for(y=0;y<col;y++) { wall[x*col+y].wall_l=1;wall[x*col+y].wall_t=1;wall[x*col+y].wall_r=1;wall[x*col+y].wall_b=1; } visited=newbool[col*row];//访问标记 for(x=0;x<row;x++) for(y=0;y<col;y++) visited[x*col+y]=false;//初始为未访问状态 position=newPOSITION[col*row];for(x=0;x<row;x++)//给每个点定位 for(y=0;y<col;y++) { position[x*col+y].x=y*CELL; position[x*col+y].y=x*CELL; position[x*col+y].index_x=y; position[x*col+y].index_y=x; }mazeedge=newMazeEdge[col*row-1];//一棵树有顶点数-1条边MessageBox(NULL,TEXT("现在开始拆墙"),TEXT("消息"),NULL);srand(time(NULL));//系统时间作随机种子x=rand()%col;//随机产生起始点y=rand()%row;Stack.push(position[y*col+x]);//迷宫入口进栈visited[y*col+x]=true;//标记已经访问过while(!Stack.empty()){w=Stack.top();while(Adj(w.index_x,w.index_y,visited,col))//如果该单元格有没有被访问过的单元格{ temp=rand()%4;if(temp==0&&(w.index_x+1<col)&&!visited[w.index_y*col+w.index_x+1])//右移{ Sleep(50); i++; mazeedge[i].x=w.x+CELL;/*记录迷宫的拆墙数据*/ mazeedge[i].y=w.y;mazeedge[i].z=w.x+CELL; mazeedge[i].w=w.y+CELL; //////////////////////////*记录每个单元格四面墙的数据 wall[w.index_y*col+w.index_x].wall_r=0;//单元格(w.index_x,w.index_y)的右墙被拆除 wall[w.index_y*col+w.index_x+1].wall_l=0;//单元格(w.index_x+1,w.index_y)的左墙被拆除 //////////////////////// Replace(hdc,w.x+CELL,w.y,w.x+CELL,w.y+CELL);//拆右竖墙 visited[w.index_y*col+w.index_x+1]=true;//标记已经访问过的单元格 Stack.push(position[w.index_y*col+w.index_x+1]);//符合条件的相邻单元格进栈 w=Stack.top();}if(temp==1&&(w.index_x-1>-1)&&!visited[w.index_y*col+w.index_x-1])//左移{ Sleep(50); i++; mazeedge[i].x=w.x;/*记录迷宫的拆墙数据*/ mazeedge[i].y=w.y;mazeedge[i].z=w.x; mazeedge[i].w=w.y+CELL; //////////////////////////*记录每个单元格四面墙的数据 wall[w.index_y*col+w.index_x].wall_l=0;//单元格(w.index_x,w.index_y)的左墙被拆除 wall[w.index_y*col+w.index_x-1].wall_r=0;//单元格(w.index_x-1,w.index_y)的右墙被拆除 //////////////////////// Replace(hdc,w.x,w.y,w.x,w.y+CELL);//拆左竖墙，左拆与右拆不一样 visited[w.index_y*col+w.index_x-1]=true;//标记已经访问过的单元格 Stack.push(position[w.index_y*col+w.index_x-1]);//符合条件的相邻单元格进栈 w=Stack.top();}if(temp==2&&(w.index_y-1>-1)&&!visited[(w.index_y-1)*col+w.index_x])//上移{ Sleep(50); i++; mazeedge[i].x=w.x;/*记录迷宫的拆墙数据*/ mazeedge[i].y=w.y;mazeedge[i].z=w.x+CELL; mazeedge[i].w=w.y; //////////////////////////*记录每个单元格四面墙的数据 wall[w.index_y*col+w.index_x].wall_t=0;//单元格(w.index_x,w.index_y)的上墙被拆除 wall[(w.index_y-1)*col+w.index_x].wall_b=0;//单元格(w.index_x,w.index_y-1)的下墙被拆除 ////////////////////////Replace(hdc,w.x,w.y,w.x+CELL,w.y);//拆横墙 visited[(w.index_y-1)*col+w.index_x]=true;//标记已经访问过的单元格 Stack.push(position[(w.index_y-1)*col+w.index_x]);//符合条件的相邻单元格进栈 w=Stack.top();}if(temp==3&&(w.index_y+1<row)&&!visited[(w.index_y+1)*col+w.index_x])//下移{Sleep(50); i++; mazeedge[i].x=w.x;/*记录迷宫的拆墙数据*/ mazeedge[i].y=w.y+CELL;mazeedge[i].z=w.x+CELL; mazeedge[i].w=w.y+CELL; //////////////////////////*记录每个单元格四面墙的数据 wall[w.index_y*col+w.index_x].wall_b=0;//单元格(w.index_x,w.index_y)的下墙被拆除 wall[(w.index_y+1)*col+w.index_x].wall_t=0;//单元格(w.index_x,w.index_y+1)的上墙被拆除 ////////////////////////Replace(hdc,w.x,w.y+CELL,w.x+CELL,w.y+CELL);//拆横墙 visited[(w.index_y+1)*col+w.index_x]=true;//标记已经访问过的单元格 Stack.push(position[(w.index_y+1)*col+w.index_x]);//符合条件的相邻单元格进栈w=Stack.top();}}Stack.pop();//回溯}WriteDocument(mazeedge,wall,i);//将迷宫拆墙数据写入txt文件}//深度优先搜索寻找迷宫路径voidDFS(HDChdc){intcol,row,entrance,exit,i,j;bool*visited=NULL;//访问标示 boolstatus(false);//走迷宫状态POSITION*position=NULL;//记录各个单元的坐标 POSITIONw;//临时中间变量 Wall*wall=NULL;//储存单元格四面墙的信息 std::stack<POSITION>Stack; std::ifstreamf("d:\\迷宫拆墙数据.txt");/*读迷宫规模数据*/f>>col>>row;//从txt文件中获取原来迷宫的规模f.close(); wall=newWall[col*row]; std::ifstreamf1("d:\\每个单元格四面墙的数据.txt");/*读迷宫墙的信息*/ for(i=0;i<col*row;i++)//从txt文档中读入每个单元格四面墙数据 f1>>wall[i].wall_l>>wall[i].wall_t>>wall[i].wall_r>>wall[i].wall_b; f1.close();srand(time(NULL));//系统时间作随机种子entrance=rand()%col;//随机在迷宫第一行和最后一行分别产生入口与出口exit=rand()%col;visited=newbool[col*row];//访问标记for(i=0;i<row;i++)for(j=0;j<col;j++)visited[i*col+j]=false;//初始为未访问状态position=newPOSITION[col*row];for(i=0;i<row;i++)//给每个点定位 for(j=0;j<col;j++) { position[i*col+j].x=j*CELL; position[i*col+j].y=i*CELL; position[i*col+j].index_x=j; position[i*col+j].index_y=i; }Stack.push(position[entrance]);//迷宫入口进栈 visited[entrance]=true;DrawRedBlock(hdc,entrance*CELL+6,6,(entrance+1)*CELL-6,CELL-6);//绘制迷宫入口 DrawRedBlock(hdc,exit*CELL+6,(row-1)*CELL+6,(exit+1)*CELL-6,row*CELL-6);//绘制迷宫出口 while(!Stack.empty()&&!status) {w=Stack.top(); while(Adj_NoWall(w.index_x,w.index_y,visited,wall,col))//如果有还没有被访问的相邻单元格并且可以访问 { if(wall[w.index_y*col+w.index_x].wall_b==0&&!visited[(w.index_y+1)*col+w.index_x])//如果下墙已经被拆除而且下边单元格没有被访问过,目标下移 { Sleep(200);DrawCell(hdc,w.x+6,w.y+CELL+6,w.x+CELL-6,w.y+2*CELL-6);//使移动目标小于单元格大小 visited[(w.index_y+1)*col+w.index_x]=true; Stack.push(position[(w.index_y+1)*col+w.index_x]);//入栈 w=Stack.top();} elseif(wall[w.index_y*col+w.index_x].wall_r==0&&!visited[(w.index_y)*col+w.index_x+1])//如果右墙已经被拆除而且右边单元格没有被访问过,目标右移 { Sleep(200);DrawCell(hdc,w.x+CELL+6,w.y+6,w.x+2*CELL-6,w.y+CELL-6);//使移动目标小于单元格大小 visited[w.index_y*col+w.index_x+1]=true; Stack.push(position[w.index_y*col+w.index_x+1]);//入栈 w=Stack.top();}elseif(wall[w.index_y*col+w.index_x].wall_l==0&&!visited[w.index_y*col+w.index_x-1])//如果左墙已经被拆除而且左边单元格没有被访问过,目标左移 { Sleep(200);DrawCell(hdc,w.x-CELL+6,w.y+6,w.x-6,w.y+CELL-6);//使移动目标小于单元格大小 visited[w.index_y*col+w.index_x-1]=true; Stack.push(position[w.index_y*col+w.index_x-1]);//入栈 w=Stack.top();}elseif(wall[w.index_y*col+w.index_x].wall_t==0&&!visited[(w.index_y-1)*col+w.index_x])//如果上墙已经被拆除而且上边单元格没有被访问过,目标上移 { Sleep(200);DrawCell(hdc,w.x+6,w.y-CELL+6,w.x+CELL-6,w.y-6);//使移动目标小于单元格大小 visited[(w.index_y-1)*col+w.index_x]=true; Stack.push(position[(w.index_y-1)*col+w.index_x]);//入栈 w=Stack.top();}if(w.index_y==row-1&&w.index_x==exit)//如果到达迷宫出口则停止搜索 { DrawRedBlock(hdc,exit*CELL+6,(row-1)*CELL+6,(exit+1)*CELL-6,row*CELL-6);//绘制迷宫出口 MessageBox(NULL,TEXT("成功走出迷宫!"),TEXT("Congratunations"),MB_ICONINFORMATION); status=true; break; } }Stack.pop();//回溯}}//广度优先搜索寻找迷宫路径voidBFS(HDChdc){intcol,row,entrance,exit,i,j;bool*visited=NULL;//访问标示 boolstatus(false);//走迷宫状态POSITION*position=NULL;//记录各个单元的坐标 POSITIONu;//临时中间变量 Wall*wall=NULL;//储存单元格四面墙的信息 std::queue<POSITION>Queue;charBuffer[20]; std::ifstreamf("d:\\迷宫拆墙数据.txt");/*读迷宫规模数据*/f>>col>>row;//从txt文件中获取原来迷宫的规模f.close(); wall=newWall[col*row]; std::ifstreamf1("d:\\每个单元格四面墙的数据.txt");/*读迷宫墙的信息*/ for(i=0;i<col*row;i++)//从txt文档中读入每个单元格四面墙数据 f1>>wall[i].wall_l>>wall[i].wall_t>>wall[i].wall_r>>wall[i].wall_b; f1.close();srand(time(NULL));//系统时间作随机种子entrance=rand()%col;//随机在迷宫第一行和最后一行分别产生入口与出口exit=rand()%col;visited=newbool[col*row];//访问标记for(i=0;i<row;i++)for(j=0;j<col;j++)visited[i*col+j]=false;//初始为未访问状态position=newPOSITION[col*row];for(i=0;i<row;i++)//给每个点定位 for(j=0;j<col;j++) { position[i*col+j].x=j*CELL; position[i*col+j].y=i*CELL; position[i*col+j].index_x=j; position[i*col+j].index_y=i; }Queue.push(position[entrance]);//迷宫入口进队列 visited[entrance]=true;DrawRedBlock(hdc,entrance*CELL+6,6,(entrance+1)*CELL-6,CELL-6);//绘制迷宫入口 DrawRedBlock(hdc,exit*CELL+6,(row-1)*CELL+6,(exit+1)*CELL-6,row*CELL-6);//绘制迷宫出口while(!Queue.empty()) {u=Queue.front();Queue.pop(); if(Adj_NoWall(u.index_x,u.index_y,visited,wall,col))//如果有还没有被访问的相邻单元格并且可以访问 {if((u.index_y+1<row)&&!visited[(u.index_y+1)*col+u.index_x]&&wall[u.index_y*col+u.index_x].wall_b==0)//如果作相邻单元格没有被访问过，并且可以被访问 { Sleep(100);DrawCell(hdc,u.x+6,u.y+CELL+6,u.x+CELL-6,u.y+2*CELL-6);//画下单元格visited[(u.index_y+1)*col+u.index_x]=true;Queue.push(position[(u.index_y+1)*col+u.index_x]);//下单元格进队列 }if((u.index_x-1>-1)&&!visited[u.index_y*col+u.index_x-1]&&wall[u.index_y*col+u.index_x].wall_l==0)//如果作相邻单元格没有被访问过，并且可以被访问 { Sleep(100);DrawCell(hdc,u.x-CELL+6,u.y+6,u.x-6,u.y+CELL-6);//画左单元格 visited[u.index_y*col+u.index_x-1]=true;Queue.push(position[u.index_y*col+u.index_x-1]);//左单元格进队列 } if((u.index_x+1<col)&&!visited[u.index_y*col+u.index_x+1]&&wall[u.index_y*col+u.index_x].wall_r==0)//如果作相邻单元格没有被访问过，并且可以被访问{