Kotlin程序员解密迷宫问题

【出自YMX笔试题】

难度系数：★★★★☆ 被考察系数：★★★★☆

题目描述：

给定一个大小为N×N的迷宫，一只老鼠需要从迷宫的左上角（对应矩阵的[0][0]）走到迷宫的右下角（对应矩阵的[N-1][N-1]），老鼠只能向两个方向移动：向右或向下。在迷宫中，0表示没有路（是死胡同），1表示有路。例如：给定下面的迷宫：

图中标粗的路径就是一条合理的路径。请给出算法来找到这样一条合理路径。

分析与解答：

最容易想到的方法就是尝试所有可能的路径，找出可达的一条路。显然这种方法效率非常低，这里重点介绍一种效率更高的回溯法。主要思路为：当碰到死胡同的时候，回溯到前一步，然后从前一步出发继续寻找可达的路径。算法的主要框架如下：

申请一个结果矩阵来标记移动的路径

if到达了目的地

打印解决方案矩阵

else(www.xing528.com)

（1）在结果矩阵中标记当前为1（1表示移动的路径）。

（2）向右前进一步，然后递归地检查，走完这一步后，判断是否存在到终点的可达的路线。

（3）如果步骤（2）中的移动方法导致没有通往终点的路径，那么选择向下移动一步，然后检查使用这种移动方法后，是否存在到终点的可达的路线。

（4）如果上面的移动方法都会导致没有可达的路径，那么标记当前单元格在结果矩阵中为0，返回false，并回溯到前一步中。根据以上框架很容易进行代码实现。示例代码如下：

程序的运行结果如下：

1 0 0 0

1 1 0 0

0 1 0 0

0 1 1 1