graph-algorithm - 这个遍历问题有解决方案吗？

Question

假设我们有一个矩阵M x N，给定两个随机指定的exit和entrance，

entrance找到exit只覆盖矩阵中每个节点一次的路径（上、下、左、右） ？

Answer 1

这显然并不总是可以解决的。假设您有这个矩阵，其中 A 是入口，B 是出口：

+---+---+
| A |   |
+---+---+
|   | B |
+---+---+

你如何解决这个问题？

Answer 2

您可以尝试的一件事是这样的：

将您的矩阵一分为二，entrance并且exit位于不同的分区中。然后，对于在分割上形成“桥梁”的每一对有效单元格，递归地查找是否存在entrance从其分区中的单元格到该单元格的有效路径，以及从该单元格的对到 的有效路径exit。如果这些对都不起作用，那么我们就找不到路径（因为如果存在这样的路径，它最终必须穿过那个分区）。

使用一个小例子，假设我们有

+---+---+
| A | B |
+---+---+
|   |   |
+---+---+

把它从中间分开给

+---+     +---+
| A |     | B |
+---+     +---+
|   | <-> |   |
+---+     +---+

<-> 是唯一有效的“桥梁”。命名那对“C”和“D”中的单元格，然后我们有

+---+     +---+
| A |     | B |
+---+     +---+
| C | <-> | D |
+---+     +---+

我们现在找到从 A 到 C 和从 D 到 B 的路径。将这些小路径拼接在一起，我们得到 A 到 C 到 D 到 B。

在 Emil 给出的示例中，无论您使用哪种方式划分该矩阵，都无法获得有效的对来进行测试，因此您可以立即得出结论，不存在这样的路径。