【深度优先搜索】一种通用万能过关方法
2023/11/20329 浏览攻略
【可以不用纸也不用空间想象力】
本方法实际上是计算机中解决迷宫问题的一种通用算法，可以方便地完成试错过程，不重不漏。
下面是对深度优先搜索的简单介绍。
定义：节点指岔路口（包括起点）
基本步骤：
在任意一个节点，按照一定的顺序（比如上右下左）尝试该节点能前往的所有方向
如果是死路，原路退回并尝试下一个方向；
如果是墙，尝试下一个方向；
如果是来路，跳过并尝试下一个方向；
如果是节点，重复以上步骤。
如果尝试完所有方向，退回上一个节点尝试下一个方向。
下面是举例：
某一关的示意图
比如图中这关：
从起点A向上到达节点B
尝试向上，是墙，尝试向右到达节点C
尝试向上，是墙，尝试向右到达节点D
尝试向上到达节点D
尝试向上到达节点E
尝试向上，发现是死路，原路退回节点E
尝试向右，发现是墙，向下是来路，尝试向左到达节点F
尝试向上到达节点G
尝试向上，发现是墙，尝试向右，发现是墙，向下是来路，尝试向左，发现是死路，退回节点G
此时节点G的所有方向均已尝试完毕，退回节点F
向右是来路，尝试向下，发现是墙，尝试向左，发现是死路，退回节点F
此时节点F的所有方向均已尝试完毕，退回节点E
此时节点E的所有方向均已尝试完毕，退回节点D
尝试向右，发现是墙，尝试向下，发现是死路，退回节点D
此时节点D的所有方向均已尝试完毕，退回节点C
尝试向下，发现是墙，向左是来路，此时节点C的所有方向均已尝试完毕，退回节点B
向下是来路，尝试向左到达节点I
尝试向上，到达终点J
这个时候肯定有人要说，「标题党！」说好的不用纸呢？
淡定淡定，上面那个只是方便大家理解流程，现在给大家讲不用纸的方法。
把当前路径记下来即可。不明白？下面是示范：
同一关的示意图，但是去掉了字母
现在我们从起点向上到达下一个节点
「上」，这表示我们经过了一个节点，这个节点在起点的上方
尝试向上，发现是墙，尝试向右，到达下一个节点
「上右」
尝试向上，发现是墙，尝试向右，到达下一个节点
「上右右」
尝试向上，到达下一个节点
「上右右上」
尝试向上，发现是死路
「上右右上上」
现在我们需要原路退回，最后一步是上，因此我们向下退回
「上右右上」
刚刚的最后一步是上，尝试下一个方向右，发现是墙，现在的最后一步是上，说明向下是来路，跳过并尝试下一个方向左，到达下一个节点
「上右右上左」
尝试向上，到达下一个节点
「上右右上左上」
尝试向上，发现是墙，尝试向右，发现是墙，当前的最后一步是上，说明向下是来路，跳过并尝试下一个方向左，发现是死路
「上右右上左上左」
现在我们需要原路退回，最后一步是左，因此我们向右退回
「上右右上左上」
刚刚的最后一步是左，说明当前节点的所有方向均已尝试完毕，现在我们需要原路退回。当前的最后一步是上，因此我们向下退回
「上右右上左」
刚刚的最后一步是上，我们需要尝试下一个方向右，当前的最后一步是左，说明右方是来路，跳过并尝试下一个方向下，发现是墙，尝试下一个方向左，发现是死路
「上右右上左左」
现在我们需要原路退回，最后一步是左，因此我们向右退回
「上右右上左」
刚刚的最后一步是左，说明当前节点的所有方向均已尝试完毕，现在我们需要原路退回。当前的最后一步是左，因此我们向右退回
「上右右上」
刚刚的最后一步是左，说明当前节点的所有方向均已尝试完毕，现在我们需要原路退回。当前的最后一步是上，因此我们向下退回
「上右右」
刚刚的最后一步是上，尝试下一个方向右，发现是墙，尝试下一个方向，发现是死路
「上右右下」
现在我们需要原路退回，最后一步是下，因此我们向上退回
「上右右」
刚刚的最后一步是下，下一个方向是左，当前的最后一步是右，说明来路是左，当前节点的所有方向均已尝试完毕，向左退回上一个节点
「上右」
刚刚的最后一步是右，下一个方向是下，发现是墙，当前的最后一步是右，说明来路是左，当前节点的所有方向均已尝试完毕，向左退回上一个节点
「上」
刚刚的最后一步是右，下一个方向是下，当前的最后一步是上，说明来路是下，跳过并尝试下一个方向左到达下一个节点
「上左」
尝试向上到达下一个节点
「上左上」
这就是终点，过关
