是填充算法是在被认为是回溯算法的迷宫中找到输出的

Question

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

Answer 1

该算法的第一步是找到所有死端。为了实现这一目标，算法将通过矩阵（例如矩阵）穿越迷宫，并用3墙标记所有地板，例如将它们放在堆栈上。因此，这个循环显然没有回溯。

第二步包括填充死胡同，直到达到交界处为止。这是通过从堆栈中获取死胡同并沿着走廊工作来完成的。仍然没有回溯。

最后一步已经是解决方案，从进入到退出的路径。如果需要的话，穿越它是微不足道的。因此，该算法既不是递归也不是回溯。