死胡同填充算法用于在迷宫中找到输出，是否被认为是一种回溯算法？

Question

3

我对回溯问题不太熟悉，最近遇到了这个迷宫问题。有很多解决迷宫问题的方法，但我想知道如何解决死路问题。

- Vaibhav Shah

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- yacc · Accepted Answer

该算法的第一步是找到所有死胡同。为了实现这一点，该算法将像遍历矩阵一样穿过迷宫，并用三堵墙标记所有楼层，例如将它们放入一个堆栈中。因此，这个循环显然不是回溯。

第二步是填充死胡同，直到遇到交叉口。这是通过从堆栈中获取一个死胡同并沿着走廊工作来完成的。仍然没有回溯。

最后一步已经是解决方案，即从入口到出口的路径。如果需要，遍历这条路径是微不足道的。因此，该算法既不是递归也不是回溯。