algorithm - 回溯 - 如何解决 "rat in a maze"的这种变体？

Question

我最近出现在一个工作面试中，我被问到一个流行的 RAT IN A MAZE 问题，其中有一个由二维数组表示的迷宫，其中分别包含 0 和 1 表示开放路径和墙壁，我们必须打印最短的路径。

我使用回溯法解决了这个问题，还打印了所有可能的路径。

但随后面试官提高了韧性级别，并让我用老鼠可以绊倒“K”个墙的新条件来解决同样的问题，其中 K 由用户输入。

现在我尝试了很多，但都没有弄清楚如果允许绊倒K墙，如何找到最短路径。我想是否可以通过动态编程来解决，但最终无法实现。

面试官也没有透露解决方案。任何人都可以解释这个问题的解决方案吗？

Answer 1

您可以使用 breadth-first search 解决此问题.

如果您还不够熟悉上面链接的基本 BFS 算法，您可能想从阅读它开始，因为下面的内容主要基于该算法。

• 对于每个单元格，我们需要存储到达该单元格所经过的墙数 - 称之为 walls .

• 从包含我们起始单元格的队列开始。

• 让 walls起始单元格的是 0 .

• 重复将当前单元格设置为等于队列的第一个元素(我们将其删除)。

  • 如果当前单元格是目标单元格，打印出路径，我们就完成了。

  • 如果当前单元格是墙，增加current.walls 1.

  • 如果 current.walls > K ，什么都不做。

  • 对于每个邻居:(墙壁和开放式单元格)

    如果neighbour.walls未初始化(意味着我们以前没有去过那里)或 current.walls < neighbour.walls (意味着新路径的墙壁更少)，
    然后设置 neighbour.wall = current.walls并添加 neighbour到队列中。

要真正能够打印出路径，请创建一个 map ，用它的 walls 映射任何单元格。到我们从那里到达那里的细胞(它是 walls )。简单地将一个单元格映射到前一个单元格是行不通的，因为如果路径上的前一个单元格具有较低的值 K，则可以覆盖该路径上的前一个单元格。 .

您也可以存储整个路径，但效率要低得多。

时间复杂度为O(rows*columns*K)空间复杂度为O(rows*columns) .

---

这里的很多复杂性是由于需要处理这样的场景:
(你可以想象这是更大网格的一部分)

如果我们有足够大的K ，我们可以穿过两堵墙(绿色路径)并在 2 步内到达右上角的单元格。

如果K不够大，我们需要绕一圈(蓝色路径)，需要走 4 步。

因此，我们进行常规 BFS，但也会跟踪每个单元格穿过了多少堵墙，因此如果我们在绕了一圈后到达右上角的单元格，我们会看到它之前是通过穿越到达的2 堵墙(而不是当前的 0 堵墙)，因此我们从那里继续前进，以防使用 2 堵墙的路径最终需要穿过太多墙。