|
3.2.3 迷宫求解问题
求迷宫中一条从入口到出口的路径的伪码算法如下:
设定当前位置的初值为入口位置;
do{
若当前位置可通,
则{
将当前位置插入栈顶; //
纳入路径
若该位置是出口位置,则算法结束;
// 此时栈中存放的是一条从入口位置到出口位置的路径
否则切换当前位置的东邻方块为新的当前位置;
}
否则
{
若栈不空且栈顶位置尚有其他方向未被探索,
则设定新的当前位置为: 沿顺时针方向旋转找到的栈顶位置的下一相邻块;
若栈不空但栈顶位置的四周均不可通,
则{ 删去栈顶位置;
// 从路径中删去该通道块
若栈不空,则重新测试新的栈顶位置,
直至找到一个可通的相邻块或出栈至栈空;
}
}
} while
(栈不空);
栈空则说明没有路径存在;
更详细的算法以及它在运行过程中栈的变化情况请见迷宫的算法演示,学员可以自设迷宫以观察不同情况。 |
|
注意:所谓当前位置可通,指的是未曾走到过的通道块。不仅不是墙,而且是既不在当前路径上,也不是曾被纳入路径后又被从路径上删除的通道块。
|
|