摘要
本文通过将规则迷宫映射为迷宫矩阵,在迷宫矩阵中搜索迷宫路径,最后再将迷宫矩阵中的标记的路径在迷宫图中画出来.本文给出了给出了详细的搜索算法和具体的图像实现方法,供大家参考.
前些天同学录上有同学上传了一个迷宫图（如图一所示），初看确是比较吓人，不放大是看不清路径的，但放大就看不到全图！要在图里手工走出很难想象的！当时有同学走出来了，以为是用程序就可以解决（后来才了解到同学是用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);
}