用c++解决数据结构的迷宫问题

问题描述:
迷宫是实验心理学中一个古典问题。以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。入口在左上方(1,1)处,出口在右下方(m,n)处。
要求求出从迷宫入口到出口有无通路,若有通路则指出其中一条通路的路径。
计算机解迷宫时,通常用的是“回溯算法”的方法,即从入口出发,顺某一方向向前探索,若能走通,则继续往前走;否则沿原路退回,换一个方向再继续探索,直至所有可能的通路都探索到为止,如果所有可能的通路都试探过,还是不能走到终点,那就说明该迷宫不存在从起点到终点的通道。
设定当前位置的初值为入口位置;
do{
若当前位置可通,
则{将当前位置插入栈顶;
若该位置是出口位置,则算法结束;
否则切换当前位置的东邻方块为
新的当前位置;

否则 {

}while (栈不空);
若栈不空且栈顶位置尚有其他方向未被探索,
则设定新的当前位置为: 沿顺时针方向旋转找到的栈顶位置的下一相邻块;
若栈不空但栈顶位置的四周均不可通,
则{删去栈顶位置;// 从路径中删去该通道块
若栈不空,则重新测试新的栈顶位置,
直至找到一个可通的相邻块或出栈至栈空;

若栈空,则表明迷宫没有通路。

你好,我是有问必答小助手,非常抱歉,本次您提出的有问必答问题,技术专家团超时未为您做出解答


本次提问扣除的有问必答次数,已经为您补发到账户,我们后续会持续优化,扩大我们的服务范围,为您带来更好地服务。