迷宫求解

凌阳教育

求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺其一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索带为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事了。

首先，在计算机中可以用如图所示的方块图表示迷宫。图中的每个方块或为通道（以空白方格表示），或为墙（以带阴影线的方块表示）。所求路径必须是简单路径，即在求得路径上不能重复出现同一通道块。

假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置“可通”，则纳入“当前路径”，并继续朝“下一个位置”探索，及切换“下一个位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周４个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一个位置”指的是“当前位置”四周４个方块上相邻的方块。假设以栈Ｓ记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作为“出栈”。

求迷宫中一条从入口到出口的路径的算法可简单描述如下：

设定当前位置的初值为入口位置；

do{

若当前位置可通，              //纳入路径

则{将当前位置插入栈顶；         //纳入路径

若该位置是出口位置，则结束；       //求得路径存放在栈中

否则切换当前位置的东邻方块为新的当前位置；

}

否则，

若栈不空且栈顶元素尚有其他方向未经探索，

则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；

若栈不空但栈顶位置的四周均不可通，

则{删去栈顶位置；

若栈不空，则重新测试新的栈顶位置，

直至找到一个可通的相邻块或出栈至栈空；

        }

}while(栈不空)

在此，尚需说明一点的是，所谓当前位置可通，指的是未曾走到过的通道块，即要求该方块位置不仅是通道块，而且既不在当前路径上（否则所求路径就不是简单路径），也不是曾经纳入过路径的通道块（否则只能在死胡同内转圈）。

typedef struct{

int ord;           //通道块在路径上的“序号”

PosType seat;  //通道块在迷宫中的“坐标位置”

int di;                    //从此通道块走向下一通道块的“方向”

}SElemType          //栈的元素类型

Status MazePath(MazeType maze,PostTypestart,PostType end){

//若迷宫maze中存在从入口start到出口end的通道，则求得一条存放在栈中（从栈底到栈顶），并返回TURE；否则返回FALSE

InitStack(S);curpos=start;   //设定“当前位置”为“入口位置”

curtep=1;                             //探索第一步

}

typedef struct{

int ord;           //通道块在路径上的“序号”

PosType seat;  //通道块在迷宫中的“坐标位置”

int di;                    //从此通道块走向下一通道块的“方向”

}SElemType          //栈的元素类型

Status MazePath(MazeType maze,PostTypestart,PostType end){

//若迷宫maze中存在从入口start到出口end的通道，则求得一条存放在栈中（从栈底到栈顶），并返回TURE；否则返回FALSE

InitStack(S);curpos=start;   //设定“当前位置”为“入口位置”

curtep=1;                             //探索第一步

do{

if(Pass(curpos)){//当前位置可以通过，即是未曾走到过的通道块}

       FootPrint(curpos);  //留下足迹

       e=(curstep,curpos,1);

       Push(S,e);                           //加入路径

       if(curpos==end)return(TRUE);//到达终点

       curpos=NextPos(curpos,1);    //下一个位置是当前位置的东邻

       curstep++;             //探索下一步

       }//if

       else{//当前位置不能通过

       if(!StackEmpty(S)){

       Pop(S,e);

       while(e.di==4&&!StackEmpty(S)){

              MarkPrint(e.seat)op(S,e);          //留下不能通过的标记，并退回一步

       }//while

       if(e.di<4){

       e.di++ush(S,e);          //换下一个方案探索

       curpos=NextPos(e.seate.di);  //设定当前位置是该方向上的相邻块

       }//if

       }//if

       }//else

}while(!StackEmpty(S));

return(FALSE);

}//MazePath

凌阳教育，全国唯一一家原厂式嵌入式培训机构，专业从事嵌入式人才培训13年，最近新开课程信息安全工程师培训，想了解更多嵌入式资料下载或者是凌阳教育的动态，请访问凌阳教育官网www.sunplusedu.com。