分配迷宫空间;
分配足迹路径空间;
初始化迷宫行数列数;
初始化迷宫元素——系统固定、用户输入;
初始化迷宫起点和终点;
初始化迷宫足迹为0
迷宫形状三种模式,用到switch()case语句。
输出路径
初始化路径为0,0表示没走过
走过的足迹坐标记录在堆栈中,将堆栈中的每一个坐标对应足迹设为1,遍历足迹二维数组,输出所有足迹即一个二维数组01的矩阵。
迷宫求解
穷举法:从入口出发,顺某方向向前探索,如能走通,则继续往前走,否则沿原路返回,换一个方向再试,直到所有可能的都探索到为止。为了保证在任何时候都有可能沿原路返回,所有要用后进先出的结构—栈来保存从入口到当前位置的路径。
当前位置是指在搜索过程中某时刻所在图中某方块的位置。若当前位置“可通”,则纳入“当前路径”,并继续朝下一个位置搜索,即切换下一个位置为当前位置,如此重复直至到达出口;若当前位置不可通,则退会到前一个通块,在这个通块的其他方向再次前进尝试,若该通道块的4个方向都不可通,则从当前路径上删除该通道块,再尝试前一个通道块,以此类推。
当前路径的最上面的一个通道块是当前路径栈中的栈顶,纳入路径相当于入栈,删除或退后就相当于出栈。
do
{
若当前位置可通
则{将当前位置插入栈顶
若当前位置是出口位置,则结束
否则切换当前位置的东邻方块为新的当前位置
}
否则{
若栈不空且栈顶位置尚有其他方向未经搜索
则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块
若栈不空但栈顶位置的四周都不通
则{ 删去栈顶位置
若栈不空,则重新测试新的栈顶位置
直到找到一个可通的相邻块或出栈至栈空
}
}
}while(栈不空)