123走迷宫宫算出的商

说明:由于迷宫的设计老鼠123走迷宮宫的入口至出口路径可能不只一条,如何求出所有的路径呢
解法:求所有路径看起来复杂但其实更简单,只要在老鼠走至出口时显示经過的路径
然后退回上一格重新选择下一个位置继续递回就可以了,比求出单一路径还简单
我们的程式只要作一点修改就可以了。

       给定一个N*N的迷宫从迷宫左上角(對应矩阵[0][0])走到迷宫右下角(对应矩阵[N-1][N-1]),只能向两方向移动:向右或向下在迷宫中0表示没有路,1表示有路

       这里使用回溯法,当碰到死胡同時回溯到前一步,然后从前一步出发继续寻找可达路径

         (3)如果(2)中的移动方向导致没有通往终点的路径,那么选择向下移动然后检查这种移动方法是否存在可以到达终点的可达路线。

         (4)如果上面的移动方法导致没有可达的路径那么标记当前的单元格在结果矩阵中为0,返回false并回溯到前一步中。

 #打印从起点到终点的路线
 #判断x和y是否是一个合理的单元
 使用回溯法找到一条从左上角到右下角的路径maze表示迷宮,x、y表示起点sol存储结果
 #判断maze[x][y]是否是一个可走的单元
 #标记当前单元为0用来表示这条路不可行,然后回溯

参考资料

 

随机推荐