开发学院软件开发数据结构 规则迷宫的一种求解思想及算法 阅读

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

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

摘要

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

前些天同学录上有同学上传了一个迷宫图(如图一所示),初看确是比较吓人,不放大是看不清路径的,但放大就看不到全图!要在图里手工走出很难想象的!当时有同学走出来了,以为是用程序就可以解决(后来才了解到同学是用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);
}
这样迷宫图就被映射为迷宫矩阵。

1 2  下一页

Tags:规则 迷宫 求解

编辑录入:爽爽 [复制链接] [打 印]
[]
  • 好
  • 好的评价 如果觉得好,就请您
      0%(0)
  • 差
  • 差的评价 如果觉得差,就请您
      0%(0)
赞助商链接