迷宫算法综述_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
2页¥3.0012页免费12页免费2页¥3.005页¥3.00 38页1下载券71页2下载券6页1下载券30页2下载券
喜欢此文档的还喜欢3页免费16页免费3页1下载券2页免费4页1下载券
迷宫算法综述|小​车​算​法
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
你可能喜欢2938人阅读
&迷宫问题就是典型的图的搜索问题，我们可以采用栈来实现迷宫的深度搜索，从而找到一条路径，但是却不是从入口到出口的最短路径；寻找最短搜索路径通常的方法是用广度优先搜索，利用队列来完成的。一般图的广度优先搜索算法可以简单描述为：Void BFS(Graph G){初始化一个队列；从G的初始点开始；if （当前的结点是目标结点）&& 搜索结束；&& else 初始点进入队列；do {取队头结点，并产生其相邻结点；if （产生的结点是目标结点）& {输出一个解；搜索结束；}if (产生的结点是新结点)& 新结点进队列} while (队头&=队尾)；}& // end_BFS如果我们要得到所有的解，只需找到一个解后输出，并不结束循环就可以了。我们来看一个例子。【问题描述】有一个迷宫，只有一个入口和一个出口，我们希望用搜索法找到一条从入口到出口的最短路径。首先应考虑怎么描述迷宫。可用二维数组mg(m,n)存储迷宫,其含义如下：&&&&& 为了解决出界问题，我们在四周加上无法通过的&墙&，也就是&哨兵&，这样可以减少判断是否出界。图10-3是用二维数组表示的一个迷宫。&&&&&&& 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1入口 Þ 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1&&&&&&& 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1&&&&&&& 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1&&&&&&& 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1&&&&&&& 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1&&&&&&& 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 1&&&&&&& 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 1&&&&&&& 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1&&&&&&& 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 1&&&&&&& 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1&&&&&&& 1 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1&&&&&&& 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 0 1 1&&&&&&& 1 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1&&&&&&& 1 1 0 1 0 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1&&&&&&& 1 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 Þ 出口&&&&&&& 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1&&& &&&&&&&&&&&&&&&&& 图10-3 迷宫的数组表示&&&&&& 现在来看一看搜索路径的选择：一般的迷宫可以从八个方向进行搜索，为了简化问题，我们考虑从以下四个方向去搜索：&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& ( i-1 , j )&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&& ( i , j -1)&&&&&&& ( i , j )&&&&&& ( i , j +1)&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& ( i+1 , j )&&&&&&&&&&&&&&&&&&&&&&&&& 图 10-4 四个搜索方向用数组表示其下标的变化（只记录其增量）如下：&&&&&&&&&&&&&&&&&&&& 1(上)&& 2(右)&& 3(下)&& 4(左) 行下标变化△i：&&&&&& -1&&&&&& 0&&&&&& 1&&&&&& 0&& 列下标变化△j：&&&&&&& 0&&&&&& 1&&&&&& 0&&&&&& -1&& 为了防止被搜索过的单元被重复搜索，也就是避免转圈或走重复的路径，于是应该将所走过的路径作上记号，在不增加额外的存储空间的情况下，可将mg修改如下：&&&&& 为了找到最短路径，我们用队列SQueue来保存搜索过的位置。搜索的规则是：选择一个可通行的位置而又没有试探过的单元p，沿四个方向作搜索，若这四个方向中有可行通路又没有搜索过的单元q，则说明从p到q有通路，将q记录在SQueue中，SQueue[m*n]是一个三元组数组，用来记录搜索过的单元, SQueue[k].x记录第k次搜索的单元q的行坐标，SQueue[k].y记录q的列坐标，SQueue[k].pre记录产生q的单元即p单元在SQueue中的下标，即记录每个搜索单元的产生轨迹，或记录其父结点，其目的是为了在找到出口后沿这个下标返回到入口处，方便最后显示这条最短路径。这四个方向都搜索完了，（修改q单元为已搜索过）；接下来从SQueue中取出对头，往下继续搜索。在搜索过程中如果遇上了出口单元，则认为已经找到了一条从入口到出口的最短路径；如果迷宫中所有可通行的道路都搜索完，都没有遇上出口单元，此时认为该迷宫是无法通过的。【数据描述】typedef struct{int x,y; //搜索位置的坐标 //表示父结点的位置}SQtypedef struct{int Deltai,D //4个搜索方向的坐标变化值}Dint mg[m+2][n+2];SQarray SQueue[Max];Direction Dchange[5];我们看看图10-3这样的迷宫,队列SQueue的变化情况：1& 2& 3& 4& 5& 6&& 7& 8&& 9& 10&& 11& 12& 13& 14&& 15&&& ...x11111111111213& ...y1234567891011101210& ...pre012345678910101112& ...&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& front&&&&&&&&& rear图10-5 队列SQueue的变化&&& 设入口地址是（1，1），出口地址是（m，n），我们来看一看迷宫问题的算法描述。【算法描述】Step1:建立迷宫数组mg[m+1][n+1]；建立搜索的四个方向下标变化变量：Dchange[1..4]；Step2:给mg周围加&哨兵&；Step3: 初始化队列：front=0；rear=0；Goout=FALSE;Step4: 入口位置入队列SQueue：rear++；SQueue[rear].x=1；SQueue[rear].y=1；SQueue[rear].pre=0; mg[1][1]=-1；（0表示入口是第一个结点，无前驱结点）； Step5: do {&&& front++; i=SQueue[front].x; j=SQueue[front].y; //出队列&&& for (d=1;d&=4;d++){&&&&&&&& //沿4个方向搜索&&&&&&& di=i+dchange[d].Deltai；dj=j+dchange[d].Deltaj； //确定新的搜索位置&&&&&&& if (!mg[di][dj]) {&&&&&& //如果新位置是未搜索通道，则将新位置入队列&&&&&&&&&& rear++; SQueue[rear].x=di；SQueue[rear].y=dj；SQueue[rear].pre=front；&&&&&&&&&& Mg[di][dj]=-1; }&&&& //标识搜索过的位置为-1&&&&&&& if (i=m && j=n){&&&&&&& //找到出口&&&&&&&&&& 打印路径；Goout=TRUE； }&& }while(front&=rear && !Goout)Step6: if (!Goout) printf(&No Pass!/n&)；（7）若flag=0 则输出&无法走出迷宫&【C源程序】#include &stdio.h&#define m 15#define n 21#define Max 500typedef struct{int x,y;&&&&&&&&&& /*搜索位置的坐标 */&&&&&&&&&& /*表示前驱点的位置 */}SQtypedef struct{int Deltai,D /*4个搜索方向的坐标变化值 */}Dint mg[m+2][n+2]={{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},{1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,1},{1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1},{1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,1},{1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1},{1,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,1},{1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,0,1,1,1,1},{1,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,1},{1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1},{1,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,1},{1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1},{1,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,0,1},{1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,1},{1,0,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1},{1,1,0,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,1},{1,1,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}};SQarray SQueue[Max];Direction Dchange[5]={{0,0},{-1,0},{0,1},{1,0},{0,-1}};void print(int k){int i,j,kk=k;do{ i=SQueue[kk].x; j=SQueue[kk].y;&& mg[i][j]=3; kk=SQueue[kk].}while(kk);printf(&& 模拟迷宫路径: # 表示最后走出迷宫的路径, -1表示探索过的路径/n&);printf(&进入-&&);for (i=1;i&=m;i++){ for (j=1;j&=n;j++)&&&& if (mg[i][j]==3) printf(&%2c&,'#');&&&&&& else printf(&%2d&,mg[i][j]);&&& if (i==m) printf(&-&走出/n&); &&&& else printf(&/n&&&&& &);}}main(){int d,i,j,di,dj,front,rear,Gfront=0;rear=0;Goout=0;rear++;SQueue[rear].x=1;SQueue[rear].y=1;SQueue[rear].pre=0; mg[1][1]=-1;do {&&& front++; i=SQueue[front].x; j=SQueue[front].y; /*出队列& */&&& for (d=1;d&=4;d++){&&&&&&&& /*沿4个方向搜索*/&& di=i+Dchange[d].D dj=j+Dchange[d].D& /*确定新的搜索位置 */&& if (!mg[di][dj]) {&&&&&&&&& /*如果新位置是未搜索通道，则将新位置入队列*/&&&&&&&&&& rear++; SQueue[rear].x=SQueue[rear].y=&&&&&&&&&& SQueue[rear].pre=&&&&& mg[di][dj]=-1; }&&&&&&&& /*标识搜索过的位置为-1 */&& if (i==m && j==n){&&&&&&&&& /*找到出口*/&&&&&&&&&& print(rear); Goout=1; }&& }&& }while(front&=rear && !Goout);if (!Goout) printf(&No Pass!/n&);}【运行结果】&&&& 模拟迷宫路径: # 表示最后走出迷宫的路径, -1表示探索过的路径进入 && #& #& #& #& #& #& #& #& #& # -1 -1& 1 -1 -1 -1& 1& 0& 0& 0& 1 &&&&&&&& 1& 1& 1& 1& 1& 1& 1& 1& 1& #& 1& 1& 1 -1& 1& 1& 1& 1& 1& 1& 1 &&&&&&&& 1& 0& 1 -1 -1 -1 -1& #& #& # -1 -1 -1 -1& 1& 0& 0& 0& 1& 0& 0 &&&&&&&& 1& 1& 1& 1& 1 -1& 1& #& 1& 1& 1& 1& 1& 1& 1& 0& 1& 0& 1& 1& 1 &&&&&&& -1 -1 -1 -1 -1 -1& 1& #& 1& #& #& #& 1& 0& 1& 0& 1& 0& 1& 0& 0 &&&&&&&& 1& 1& 1& 1& 1& 1& 1& #& 1& #& 1& #& 1& 0& 1& 1& 1& 0& 1& 1& 1 &&&&&&&& 1& 0& 1 -1 -1& #& #& #& 1& #& 1& #& 1& 0& 0& 0& 0& 0& 1& 0& 1 &&&&&&&& 1& 1& 1& 1& 1& #& 1& 1& 1& #& 1& #& 1& 1& 1& 1& 1& 1& 1& 1& 1 &&&&&&&& 1& 0& 0& 0& 1& #& #& #& #& #& 1& #& #& #& #& #& 1& 0& 1& 0& 1 &&&&&&&& 1& 1& 1& 0& 1& 1& 1 -1& 1& 1& 1& 1& 1& 1& 1& #& 1& 0& 1& 1& 1 &&&&&&&& 1& 0& 1& 0& 0& 0& 1 -1& 1& #& #& #& #& #& #& #& 1& 0& 0& 0& 0 &&&&&&&& 1& 1& 1& 0& 1& 0& 1& 1& 1& #& 1& 1& 1& 1& 1& 1& 1& 0& 1& 0& 1 &&&&&&&& 0& 0& 1& 0& 1& 0& 1 -1 -1& #& #& #& #& #& #& #& 1& 0& 0& 0& 0 &&&&&&&& 1& 0& 1& 0& 1& 1& 1 -1& 1& 1& 1& 1& 1 -1& 1& #& 1& 1& 1& 1& 1 &&&&&&&& 1& 0& 0& 0& 1& 0& 1 -1 -1 -1 -1 -1 -1 -1& 1& #& #& #& #& #& # -& 走出 【说明】算法的时间复杂度取决于搜索单元的个数，即数组SQueue的使用大小，最坏的情况是 。【实验题】1．& 将上题迷宫的4个搜索方向改成8个搜索方向，看看运行的结果怎样；2．& 改进上面的程序，求出所有的通路，并统计从迷宫的入口到出口共有几条通路；3．& 将队列改成栈来解决迷宫问题，并比较这两种方法的差异。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：46135次
排名：千里之外
原创：22篇
转载：10篇
评论：17条迷宫问题的算法(优于广度优先,深 Other Games 其他
182万源代码下载-
&文件名称: 迷宫问题的算法(优于广度优先,深度优先
& & & & &&]
&&所属分类:
&&开发工具: C++
&&文件大小: 10 KB
&&上传时间:
&&下载次数: 79
&&提 供 者:
&详细说明：迷宫问题的算法(优于广度优先,深度优先-maze of algorithm (priority than breadth, depth priority
文件列表(日期：~)(点击判断是否您需要的文件，如果是垃圾请在下面评价投诉):
&&&&MG.EXE
&[]:不能解压或下载失败&[]:不能解压或下载失败
&近期下载过的用户:
&相关搜索:
&输入关键字，在本站182万海量源码库中尽情搜索：
&[] - A star 算法类的实现(算法接口，针对迷宫问题设计)
&[] - 输入一个任意大小的迷宫， 用栈求出一条走出迷宫的路径， 并显示在屏幕上。
&[] - 很多呀，呵呵案例一 贪吃蛇游戏案例二 计算器案例三 黑白棋游戏案例四 迷宫问题案例五 扫地雷游戏案例六 速算24案例七 数据结构CAI系统案例八 进程调度案例九 存储管理分区分配算法案例十 通讯录案例十一 学生成绩管理案例十二 工资管理案例十三 图书借阅管理案例十四 教师工作量计算
&[] - 数据结构的课程设计
&[] - 我不知道这本书算不算数据结构最经典的教材了?!但我知道错过这本书你将找不到更好的数据结构教材!周围很多人受益于此书菲浅,而且是PDF清晰版的!值得阅读
&[] - 迷宫问题的算法,用c实现的
&[] - 本程序用vc来实现小球走迷宫,非常经典,非常有意思!
&[] - 用VC开发的迷宫老鼠源码
&[] - 一份很好的linux入门资料
&[] - VC++做的闹钟程序 功能很多,并且界面很漂亮.基于深度及广度优先搜索的迷宫问题的演示 -C#应用
||||||||||||
当前位置 &
Tag:,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
基于深度及广度优先搜索的迷宫问题的演示
发表日期：
1&时间复杂度分析
由于该图采用邻接矩阵存储，整个算法遍历的过程所花费的时间复杂度为该矩阵的N(row*col)。而由于其需要分别访问已经定位，需要进行分别2次操作，如下：
visited&=&new&bool[col*row];//访问标记
for&(i=0;&i&&i++)
for&(j=0;&j&&j++)
visited[i*col+j]&=&//初始为未访问状态
position&=&new&POSITION[col*row];
for&(i=0;&i&&i++)//给每个点定位
for&(j=0;&j&&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分别表示迷宫的行和列）。
2&空间复杂度分析
5.2.1&深度优先搜索空间复杂度分析
当进行深度优先搜索时，所遍历的最短路径即为单一路径，因此最好的空间复杂度是（），而最坏情况为（），即通过了最大的回溯之后才找到终点路径。
5.2.2广度优先搜索空间复杂度分析
当进行广度优先搜索的时候，路径经过所有可能的路径，即最大为，因此，空间复杂度为（）。
#include&windows.h&
#include&iostream&
#include&ctime&
#include&stdlib.h&
#include&fstream&
#include&stack&
#include&queue&
const int CELL = 25;// 单元像素宽
const int W = 15;
// 迷宫宽度
const int H = 15;
// 迷宫高度
struct POSITION//每一个单元格的左上坐标
int//单元格横坐标(单位pixel)
int//单元格纵坐标
int index_x;//单元格横标
int index_y;//单元格纵标
struct MazeEdge//储存的是原来迷宫所拆的墙，下次生成迷宫和原来一样拆
struct Wall
int wall_r;//右墙数据
int wall_l;//左墙数据
int wall_t;//上墙数据
int wall_b;//下墙数据
LRESULT CALLBACK Wndoc ( HWND, UINT, WPARAM, LPARAM);//窗口函数
void DrawWhiteGround (HDC hdc);//将整个客户区绘制为白色
void DrawRedBlock (HDC hdc, int l, int t, int r, int b);//绘制迷宫起始点与终止点
void DrawRect (HDC hdc, int l, int t, int r, int b);//绘制单元方格
void DrawCell (HDC hdc, int l, int t, int r, int b);//绘制移动方块
void DrawGamePlace(HDC hdc, int col, int row); //在客户区绘满单元格
void DrawPath(HDC hdc, int w, int h);//迷宫拆墙
bool Adj(int x, int y, bool* visited, int col);//判断该单元格是否有没有被访问的相邻单元格
bool Adj_NoWall(int x, int y, bool* visited, Wall* wall, int col);//判断该单元格是否有没有被访问的相邻单元格并且周围没有墙可以访问
void Replace (HDC hdc, int x, int y, int z, int k);//拆墙(用白色划线替换红色划线)
void WriteDocument (MazeEdge* mazeedge, Wall* wall, int i);//将迷宫拆墙数据写入txt文件中
bool ReadDocument (HDC hdc);//从txt文件中读取迷宫拆墙数据
void DFS (HDC hdc);//深度优先搜索寻找迷宫路径
void BFS (HDC hdc);//广度优先搜索寻找迷宫路径
//---------------------------------------------------------------
int WINAPI WinMain ( HINSTANCE hInstance,
HINSTANCE hPrevInstance,
szCmdLine,
static char AppName[]="ToyBrick";//窗口类名
//消息结构
WNDCLASSEX
//定义一个整型变量来取得窗口的宽度
wndclass.cbSize
= sizeof(wndclass);
wndclass.style
= CS_HREDRAW|CS_VREDRAW;//窗口类型
wndclass.lpfnWndProc = WndP
//窗口处理函数为 WndProc
wndclass.cbClsExtra
//窗口类无扩展
wndclass.cbWndExtra
//窗口实例无扩展
wndclass.hInstance
//当前实例句柄
wndclass.hIcon
= LoadIcon (NULL, IDI_);//默认图标
wndclass.hCursor
= LoadCursor (NULL,IDC_ARROW);
//箭头光标
wndclass.hbrBackground = (HBRUSH)GetStockObject (WHITE_BRUSH); //背景为黑色
wndclass.lpszMenuName = NULL;
//窗口中无菜单
wndclass.lpszClassName = AppN
//类名为"ToyBrick"
wndclass.hIconSm
= LoadIcon (NULL, IDI_INFORMATION);
//----------------------------------窗口类的注册-----------------------------------------
if(!RegisterClassEx (&wndclass))//如果注册失败则发出警报声音，返回FALSE
MessageBeep(0);
return FALSE;
// 获取显示器分辨率的X值iScreenWide，将程序窗口置于屏幕中央
iScreenWide=GetSystemMetrics (SM_CXFULLSCREEN);
hwnd =CreateWindow (
//窗口类名
"深度、广度优先搜索迷宫",//窗口实例的标题名
WS_MINIMIZEBOX|WS_SYSMENU , //窗口的风格
iScreenWide/2-W*CELL/2,
//窗口左上角横坐标(X)
//窗口左上角纵坐标(Y)
(W+0.3)*CELL,
//窗口的宽，而不是客户区的宽
(H+1.2)*CELL,
//窗口的高 ，而不是客户区的高
//窗口无父窗口
//窗口无主菜单
hInstance,
//创建此窗口的应用程序的当前句柄
//不使用该值
if(!hwnd) return FALSE;
MessageBox(NULL,TEXT("主程序:彭俊威"), TEXT("数据结构课程设计"),MB_ICONINFORMATION);
//显示窗口
ShowWindow (hwnd,iCmdShow);
//绘制客户区
UpdateWindow (hwnd);
//消息循环
while (GetMessage (&msg, NULL, 0, 0))
TranslateMessage (&msg);
DispatchMessage (&msg);
//消息循环结束即程序终止时将消息返回系统
return msg.wP
//-------------------窗口过程函数WndProc-----------------------------
LRESULT CALLBACK WndProc ( HWND
iMsg,WPARAM wParam,LPARAM lParam )
PAINTSTRUCT
//char Buffer[20];
switch (iMsg)
//WM_PAINT(窗口第一次生成时执行,WM_PAINT将图从内存拷到屏幕上)
case WM_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);
//WM_DESTROY(响应关闭窗口动作)
case WM_DESTROY:
PostQuitMessage (0);
return DefWindowProc (hwnd, iMsg, wParam, lParam);
//////////////////////////////////////////////////////////
//将整个客户区绘制为白色
void DrawWhiteGround (HDC hdc)
std::ifstream f ("d:\\迷宫拆墙数据.txt");
f.close();
HBRUSH hbrush = CreateSolidBrush(RGB(255,255,255));
SelectObject(hdc, hbrush);
Rectangle(hdc, 0, 0, col*CELL, row*CELL);
DeleteObject(hbrush);
//绘制迷宫起始点与终止点
void DrawRedBlock (HDC hdc, int l, int t, int r, int b)
HBRUSH hbrush = CreateSolidBrush(RGB(255,0,0));
SelectObject (hdc, hbrush);
Rectangle(hdc, l, t, r, b);
DeleteObject(hbrush);
//拆墙(用白色划线替换红色划线)
void Replace (HDC hdc, int x, int y, int z, int k)
hpen = CreatePen(PS_SOLID, 1, RGB(255,255,255));
SelectObject(hdc, hpen);
MoveToEx (hdc,x, y,NULL);
LineTo (hdc, z, k);
DeleteObject(hpen);
//画单元格，后面四个参数依次为左上坐标和右下坐标
void DrawRect (HDC hdc, int l, int t, int r, int b)
MoveToEx (hdc, l, t, NULL);
//将起始点移动到(l,t)
LineTo (hdc, r, t);
LineTo (hdc, r, b);
LineTo (hdc, l, b);
LineTo (hdc, l,t);
//用绿色画刷画移动目标
void DrawCell (HDC hdc, int l, int t, int r, int b)
hbrush=CreateSolidBrush(RGB(0,255,0));
// 绿色画刷
SelectObject(hdc,hbrush);
Rectangle(hdc,l, t, r, b);
DeleteObject (hbrush);
//在客户区绘满单元格
void DrawGamePlace(HDC hdc, int col, int row)
HPEN hpen1;
hpen1=CreatePen(PS_SOLID,1,RGB(255,0,0));
//绘制区域方格线(红色)
SelectObject(hdc,hpen1);
for (i=0; i& i++)
for(j=0; j& j++)
DrawRect (hdc, j*CELL, i*CELL, (j+1)*CELL, (i+1)*CELL);
DeleteObject(hpen1);
//迷宫拆墙
void DrawPath(HDC hdc, int col, int row)
int x, y, temp, i(-1);
// 访问标记
POSITION*//储存每个单元格的坐标
std::stack&POSITION&S
MazeEdge *
Wall*//储存每个单元格的墙的情况
wall = new Wall[col*row];//申请col*row个单元格
for (x=0; x& x++)//请所有单元格的四面墙初始化为都有状态
for (y=0; y& 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 = new bool[col*row];//访问标记
for (x=0; x& x++)
for (y=0; y& y++)
visited[x*col+y] = false;//初始为未访问状态
position = new POSITION[col*row];
for (x=0; x& x++)//给每个点定位
for (y=0; y& y++)
position[x*col+y].x = y*CELL;
position[x*col+y].y = x*CELL;
position[x*col+y].index_x =
position[x*col+y].index_y =
mazeedge = new MazeEdge[col*row-1];//一棵树有顶点数-1条边
MessageBox(NULL, TEXT("现在开始拆墙"), TEXT("消息"), NULL);
srand (time(NULL));//系统时间作随机种子
x = rand()%//随机产生起始点
y = rand()%
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);
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);
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);
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);
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文件
//深度优先搜索寻找迷宫路径
void DFS (HDC hdc)
int col, row, entrance, exit, i,
bool* visited = NULL;//访问标示
bool status(false);//走迷宫状态
POSITION* position = NULL;//记录各个单元的坐标
POSITION//临时中间变量
Wall* wall = NULL;//储存单元格四面墙的信息
std::stack&POSITION& S
std::ifstream f("d:\\迷宫拆墙数据.txt");
/*读迷宫规模数据*/
f&&col&&//从txt文件中获取原来迷宫的规模
f.close();
wall = new Wall[col*row];
std::ifstream f1("d:\\每个单元格四面墙的数据.txt"); /*读迷宫墙的信息*/
for (i=0; i&col* 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()%//随机在迷宫第一行和最后一行分别产生入口与出口
exit = rand()%
visited = new bool[col*row];//访问标记
for (i=0; i& i++)
for (j=0; j& j++)
visited[i*col+j] = false;//初始为未访问状态
position = new POSITION[col*row];
for (i=0; i& i++)//给每个点定位
for (j=0; j& j++)
position[i*col+j].x = j*CELL;
position[i*col+j].y = i*CELL;
position[i*col+j].index_x =
position[i*col+j].index_y =
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();
else if (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();
else if (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();
else if (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;
Stack.pop();//回溯
//广度优先搜索寻找迷宫路径
void BFS (HDC hdc)
int col, row, entrance, exit, i,
bool* visited = NULL;//访问标示
bool status(false);//走迷宫状态
POSITION* position = NULL;//记录各个单元的坐标
POSITION//临时中间变量
Wall* wall = NULL;//储存单元格四面墙的信息
std::queue&POSITION& Q
char Buffer[20];
std::ifstream f("d:\\迷宫拆墙数据.txt");
/*读迷宫规模数据*/
f&&col&&//从txt文件中获取原来迷宫的规模
f.close();
wall = new Wall[col*row];
std::ifstream f1("d:\\每个单元格四面墙的数据.txt"); /*读迷宫墙的信息*/
for (i=0; i&col* 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()%//随机在迷宫第一行和最后一行分别产生入口与出口
exit = rand()%
visited = new bool[col*row];//访问标记
for (i=0; i& i++)
for (j=0; j& j++)
visited[i*col+j] = false;//初始为未访问状态
position = new POSITION[col*row];
for (i=0; i& i++)//给每个点定位
for (j=0; j& j++)
position[i*col+j].x = j*CELL;
position[i*col+j].y = i*CELL;
position[i*col+j].index_x =
position[i*col+j].index_y =
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)//如果作相邻单元格没有被访问过，并且可以被访问
Sleep (100);
DrawCell (hdc, u.x+CELL+6, u.y+6, u.x+2*CELL-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_y-1&-1)&&!visited[(u.index_y-1)*col+u.index_x]&&wall[u.index_y*col+u.index_x].wall_t==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_y==row-1&&u.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);
//判断该单元格是否有没有被访问的相邻单元格
bool Adj(int x, int y, bool* visited, int col)
if((x-1&-1)&&!visited[y*col+x-1]||(x+1&W)&&!visited[y*col+x+1]||\
y-1&-1&&!visited[(y-1)*col+x]||y+1&H&&!visited[(y+1)*col+x])
return true;
return false;
//判断该单元格是否有没有被访问的相邻单元格并且周围没有墙可以访问
bool Adj_NoWall(int x, int y, bool* visited, Wall* wall, int col)
if((x-1&-1)&&!visited[y*col+x-1]&&wall[y*col+x].wall_l==0||(x+1&W)&&!visited[y*col+x+1]&&wall[y*col+x].wall_r==0||\
y-1&-1&&!visited[(y-1)*col+x]&&wall[y*col+x].wall_t==0||y+1&H&&!visited[(y+1)*col+x]&&wall[y*col+x].wall_b==0)
return true;
return false;
//将迷宫拆墙数据写入txt文件中
void WriteDocument (MazeEdge* mazeedge, Wall* wall, int i)
std::ofstream f("d:\\迷宫拆墙数据.txt");
f&&W&&" "&&H&&std:://写入拆墙数据
for (j=0; j&i+1; j++)
f&&mazeedge[j].x&&" "&&mazeedge[j].y&&" "\
&&mazeedge[j].z&&" "&&mazeedge[j].w&&std::
f.close();
std::ofstream f1("d:\\每个单元格四面墙的数据.txt");//写入每个单元格四面墙的数据
for (j=0; j&i+2; j++)
f1&&wall[j].wall_l&&" "&&wall[j].wall_t&&" "\
&&wall[j].wall_r&&" "&&wall[j].wall_b&&std::
f1.close();
//从txt文件中读取迷宫拆墙数据
bool ReadDocument (HDC hdc)
int col, row,
MazeEdge *
std::ifstream f ("d:\\迷宫拆墙数据.txt");
if (f.fail())//打开文件失败
return false;
f.close();
DrawGamePlace(hdc, col, row);//在客户区绘满红色单元格
mazeedge = new MazeEdge[col*row-1];
f.open("d:\\迷宫拆墙数据.txt");
for (i=0; i&col*row-1; i++)//从txt文档中读入数据
f&&mazeedge[i].x&&mazeedge[i].y&&\
mazeedge[i].z&&mazeedge[i].w;
f.close();
for (i=0; i&col*row-1; i++)//拆墙
Replace(hdc, mazeedge[i].x, mazeedge[i].y, mazeedge[i].z, mazeedge[i].w);
return true;
程序非原创，在开源中国有类似的。
基于c++win32编程。
上一篇： （人气：722）
下一篇：（人气：636）
教程搜索服务
本月文章推荐
项目外包信息
网络编程文章分类
站长工具：
实用工具：
Copyright &
All rights reserved | 沪ICP备号