规则迷宫的一种求解思想及算法

核心提示：摘要本文通过将规则迷宫映射为迷宫矩阵,在迷宫矩阵中搜索迷宫路径,最后再将迷宫矩阵中的标记的路径在迷宫图中画出来.本文给出了给出了详细的搜索算法和具体的图像实现方法,供大家参考.前些天同学录上有同学上传了一个迷宫图（如图一所示），初看确是比较吓人，规则迷宫的一种求解思想及算法，不放大是看不清路径的，但放大就看不到全图！要

摘要

本文通过将规则迷宫映射为迷宫矩阵,在迷宫矩阵中搜索迷宫路径,最后再将迷宫矩阵中的标记的路径在迷宫图中画出来.本文给出了给出了详细的搜索算法和具体的图像实现方法,供大家参考.

前些天同学录上有同学上传了一个迷宫图（如图一所示），初看确是比较吓人，不放大是看不清路径的，但放大就看不到全图！要在图里手工走出很难想象的！当时有同学走出来了，以为是用程序就可以解决（后来才了解到同学是用Fireworks的Magic Wind功能走出来的），但自己写程序时却一直没有想到比较理想的方法。

图一 迷宫原图

后来用Photoshop打开仔细观察发现迷宫非常规则，即可走的道路和障碍物的宽度都相同（此迷宫中为一个像素的宽度），而其长度则都是其宽度的整数倍，因此迷宫的主体部分为矩形，且迷宫边界除了出口和入口其他都是封闭的，我们不妨称其为规则迷宫。如果能够把迷宫主体转换为简单的数字矩阵，矩阵由0，1组成，0对应道路，1对应障碍物，迷宫中的最小单位（长宽为道路宽度的矩形）对应矩阵中的一个元素（此迷宫即为一个像素对应一个矩阵元素），这样的矩阵就和迷宫完全一一映射了，我们不妨称这样得到的矩阵为迷宫矩阵，而在迷宫矩阵中走出来就是搜索一条入口和出口元素之间的0元素通道，这样就容易多了！说做就做。

(一)、打开VC++6.0,为了简单起见建立一个基于Dialog的MFC程序mazes工程,并将迷宫的主体部分位图（只截取了主体部分，为601*401像素，因此迷宫矩阵大小也应为601*401）作为位图资源(IDB_ BITMAP1）选入工程，下面的代码是重载OnPaint()函数将迷宫显示在对话框上： void CMazesDlg::OnPaint()
{
　if (IsIconic())
　　{
　//此处为VC++自动生成,在此省略.
　　　　......
　　}
　　else　　　　//以下为所加代码.
　　{
　//类成员 bool first　表示初始化时将位图选入设备并显示。
　　　　if(!first){
　m_bitmap.LoadBitmap(IDB_BITMAP1);

　　　　　　//在CmazesDlg.h中已经定义类成员
　　　　　　CBitmap m_bitmap;
　　　　　　memdc.CreateCompatibleDC(NULL);

　　　　　　//在CmazesDlg.h中已经定义类成员　　　　
　　　　　　CDC memdc;

　　　　　　memdc.SelectObject(&m_bitmap);
　　　　　　m_bitmap.GetObject(sizeof(bm),&bm);

　　　　　　//在CmazesDlg.h中已经定义类成员　　　　
　　　　　　BITMAP bm;

　　　　　　//hdc 取得memdc 的值供后面使用。
　　　　　　hdc=memdc;

　　　　　　//在CmazesDlg.h中已经定义类成员　　　　　　
　　　　　　HDC hdc;

　　　　　　//初始化完成.
　　　　　　first=true;
　　　　}
　　　　CClientDC clientdc(this);　　//此处为对话框初始化和重画时显示迷宫原图的代码。
　　　　clientdc.BitBlt(10,10,bm.bmWidth+10,bm.bmHeight+10,&memdc,0,0,SRCCOPY);
　　　　if(success) setcolor(XS,YS);　　//此处为重画迷宫路径,函数见后面.
　　　　CDialog::OnPaint();
　　}
}(二)、下面的代码为迷宫映射为迷宫矩阵int mazelab[XM][YM](为公共变量矩阵)：

//点击按钮进行转换.
void CMazesDlg::OnButget()　　
{
　//类成员 bool success 　表示是否成功搜索到迷宫路径。
　　success=false;
　　int x,y;
　　MessageBox("开始将迷宫转换为矩阵!","转化",MB_OK);
　　for(x=0;x<601;x++)
　　for(y=0;y<401;y++)
　　{
　if(GetPixel(hdc,x,y)==0)　
　　　　　　mazelab[x][y]=1;
　　　　　　// GetPixel ()取得像素颜色，为0表示黑色（障碍物），对应迷宫矩阵值1。
　　　　else　
　　　　　　mazelab[x][y]=0;
　　　　　　//因为迷宫只有黑白两色，非黑即白,可走的道路对应迷宫矩阵值为0 。
　　　　flags[x][y]=0;
　　　　//公共变量矩阵flags[MX][MY]用于搜索迷宫路径时作标记，表示是否来过此处，
　　　　//现对其初始化，0表示未来过，1表示来过。
　　}
　　//将入口和出口缩小为一个元素,减少搜索量.
　　mazelab[0][200]=1,
　　//入口为mazelab[0][201],即mazelab[XS][YS],
　　mazelab[0][202]=1,
　　//出口为mazelab[600][201],即mazelab[XE][YE].
　　mazelab[600][200]=1,
　　//这些数据的取得是通过测试得到的,在此省略.
　　mazelab[600][202]=1;
　　MessageBox("成功将迷宫转换为矩阵!","成功转化",MB_OK);
}这样迷宫图就被映射为迷宫矩阵。