algorithm - 在迷宫中寻找输出的死胡同填充算法是否被视为回溯算法？

Question

我是回溯问题的新手，偶然发现了这个迷宫问题。有很多解决迷宫问题的方法。但我想知道死胡同填充问题。

Answer 1

该算法的第一步是找到所有死胡同。为实现这一点，该算法将像通过矩阵一样遍历迷宫，并用 3 面墙标记所有楼层，比如将它们放在堆栈上。所以这个循环显然不是回溯。

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

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