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

核心提示：(三)、下面的search()函数即是在已经取得的迷宫矩阵中进行搜索，bool search(int x,int y,int dir) //dir 表示搜索方向{bool subway=false,noway=false,east=false,west=false,north=false,south=false;//s

(三)、下面的search()函数即是在已经取得的迷宫矩阵中进行搜索。bool search(int x,int y,int dir)　 //dir 表示搜索方向
{
　bool subway=false,noway=false,east=false,west=false,north=false,south=false;
　　//subway 表示是否有左右方向的分杈子路，noway 表示是否可以继续往前走。
　　//east ,west, south, north 分别表示是否有往东，西，南，北的分叉子路
　　while(!subway && !noway)
　　{
　switch(dir)
　　　　{
　case E:　　　　　//往东走，在图中即为往右走。
　　　　　　x++;
　　　　　　if(x==XM-1) noway=true;
　　　　//检测是否越界。以下三句为检测是否有往前，往右，往左分叉子路，下同。
　　　　　　if(x<(XM-1) && mazelab[x+1][y]){
　noway=true,east=false;
　　　　　　} else
　　　　　　　　east=true;

　　　　　　if(y<(YM-1) && !(mazelab[x][y+1])){
　south=true,subway=true;
　　　　　　}
　　　　　　if(y>0 && !(mazelab[x][y-1])){
　north=true,subway=true;
　　　　　　}
　　　　　　break;
　　　　 case W:　　　　　//往西走，在图中即为往左走。
　　　　　　x--;
　　　　　　if(x==0) noway=true;
　　　　　　if(x>0 && mazelab[x-1][y]){
　noway=true,west=false;
　　　　　　} else
　　　　　　　　west=true;
　　　　　　if(y<(YM-1) && !(mazelab[x][y+1])){
　south=true,subway=true;
　　　　　　}
　　　　　　if(y>0 && !(mazelab[x][y-1])){
　north=true,subway=true;
　　　　　　}
　　　　　　break;
　　　　 case S:　　　　　//往南走，在图中即为往下走。
　　　　　　 y++;
　　　　 　　if(y==YM-1) noway=true;
　　　　　　if(y<(YM-1) && mazelab[x][y+1]){
　noway=true,south=false;
　　　　　　} else
　　　　　　　　south=true;
　　　　　　if(x<(XM-1) && !(mazelab[x+1][y])){
　east=true,subway=true;
　　　　　　}
　　　　 　　if(x>0 && !(mazelab[x-1][y])){
　west=true,subway=true;
　　　　 　　}
　　　　　　break;
　　　　 case N:　　　　　//往北走，在图中即为往上走。
　　　　　　 y--;
　　　　 　　if(y==0) noway=true;
　　　　　　if(y>0 && mazelab[x][y-1]){
　noway=true,north=false;
　　　　　　} else
　　　　　　　　north=true;
　　　　　　if(x<(XM-1) && !(mazelab[x+1][y])){
　east=true,subway=true;
　　　　　　}
　　　　 　　if(x>0 && !(mazelab[x-1][y])){
　west=true,subway=true;
　　　　 　　}
　　　　　　break;
　　　　}
　　}
　　if(x==XE && y==YE) return true;　　//到达终点，成功返回。
　　if(!subway && noway) return false ;
　　//前进方向无路可走且没有左右分叉子路，返回失败，即此路不通。
　　if(!flags[x][y])
　　　　flags[x][y]=1;
　　 　　//迷宫中往往有回路，在分叉路口作标记
　　　　//表示已经来过，防止程序在此转圈，无限迭代而失败。
　　else
　　　　return false ;
　　//标记为1，表示已经来过此处，返回失败，即此路不通。
　　if(subway)　　　　　　//存在分叉子路，迭代搜索。
　　{
　if(east)　east=search(x,y,E);　　 //有往东的子路，继续往东搜索。
　　　　if(south) south=search(x,y,S);　　 //有往南的子路，继续往南搜索。
　　　　if(west)　west=search(x,y,W);　　 //有往西的子路，继续往西搜索。
　　　　if(north) north=search(x,y,N);　　 //有往北的子路，继续往北搜索。
　　}
　　//根据在分叉路口的是否成功迭代返回作标记方向，后面根据此标记方向画路径
　　if(east)　mazelab[x][y]=-1;　　　　// -1表示在此分叉路口往东走可以走到出口，
　　if(south) mazelab[x][y]=-2;　　　　// -2 表示在此分叉路口往南走可以走到出口，
　　if(west)　mazelab[x][y]=-3;　　　　// -3表示在此分叉路口往西走可以走到出口，
　　if(north) mazelab[x][y]=-4;　　　　// -4表示在此分叉路口往北走可以走到出口。
　　 return (east||west||south||north) ;　　　　//返回此分叉路口的最终搜索结果。
}(四)、下面是根据搜索结果在原迷宫图上画出迷宫图解。 void CMazesDlg::setcolor(int x,int y)
{
　int dir;
　　CDC* cdc=GetDC();
　　CPen newPen;
　　newPen.CreatePen(PS_SOLID,1, RED);　　　//选用红笔画出。
　　CPen *oldPen = cdc->SelectObject(&newPen);
　　cdc->MoveTo(x+5,y+10);　　　　　　//将起始点选在左边入口处。
　　while(x!=XE|| y!=YE){
　if(mazelab[x][y]<0)　　//在分叉路口处，根据所标 方向画线。
　　　　{
　cdc->LineTo(x+10,y+10);
　　　　　　cdc->MoveTo(x+10,y+10);
　　　　　　dir=mazelab[x][y];
　　　　}　　　　　 //画迷宫路径
　　　　if(dir==-1) x++;　　　　//在非分叉路口，根据上一个方向往继续前走。
　　　　if(dir==-2) y++;
　　　　if(dir==-3) x--;
　　　　if(dir==-4) y--;
　　}
　　cdc->LineTo(XE+15,YE+10);　　//画到出口处。
　　cdc->SelectObject(oldPen);
　　newPen.DeleteObject();
}(五)、在按钮事件响应函数中调用search(),和setcolor()画出迷宫路径图解. void CMazesDlg::OnOK()
{
　MessageBox("开始搜索迷宫路径!","提示",MB_OK);
　　mazelab[XS][YS]=-1;
　　if(search(XS,YS,E))　　　　　　//从左边入口开始往东进行搜索.
　　{
　MessageBox("搜索迷宫路径成功,路径如红色所示!","成功提示",MB_OK);
　　　　CMazesDlg::setcolor(XS,YS);　　//从左边入口处开始画路线.
　　　　success=true;　　　　//搜索成功
　　}
}至此,迷宫已经走了出来,最后运行结果如图二所示.