【摘要】：在迷宫中，0表示没有路，1表示有路。如果上面的移动方法都会导致没有可达的路径，那么标记当前单元格在结果矩阵中为0，返回false，并回溯到前一步中。示例代码如下：程序的运行结果如下：1 0 0 01 1 0 00 1 0 00 1 1 1
【出自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
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
