从入口开始广度优先搜索所有可到达的方格入队,再扩展队首的方格,直到搜索到出口时算法结束。
数学模型:
根据问题描述,把迷宫看作一个图,用邻接矩阵存储。然后是解决上下左右移动的问题,上下移动时坐标x相应的减加1,坐标y不变;左右移动时坐标y相应减加1,坐标x不变。所以,我们可以数组fx[4]={1,-1,0,0}, fy[4]={0,0,-1,1};来模拟上下左右搜索时下标的变化。
另外,我们还要避免搜索时下标出界,即超出迷宫的范围。为了统一处理边界问题,我们在原迷宫的四周各加一道“墙”,这样处理边界就可以与处理迷宫内的墙用同一算法了。