假设我们有一个矩阵M x N
,给定两个随机指定的exit
和entrance
,
entrance
找到exit
只覆盖矩阵中每个节点一次的路径(上、下、左、右) ?
这显然并不总是可以解决的。假设您有这个矩阵,其中 A 是入口,B 是出口:
+---+---+
| A | |
+---+---+
| | B |
+---+---+
你如何解决这个问题?
您可以尝试的一件事是这样的:
将您的矩阵一分为二,entrance
并且exit
位于不同的分区中。然后,对于在分割上形成“桥梁”的每一对有效单元格,递归地查找是否存在entrance
从其分区中的单元格到该单元格的有效路径,以及从该单元格的对到 的有效路径exit
。如果这些对都不起作用,那么我们就找不到路径(因为如果存在这样的路径,它最终必须穿过那个分区)。
使用一个小例子,假设我们有
+---+---+
| A | B |
+---+---+
| | |
+---+---+
把它从中间分开给
+---+ +---+
| A | | B |
+---+ +---+
| | <-> | |
+---+ +---+
<-> 是唯一有效的“桥梁”。命名那对“C”和“D”中的单元格,然后我们有
+---+ +---+
| A | | B |
+---+ +---+
| C | <-> | D |
+---+ +---+
我们现在找到从 A 到 C 和从 D 到 B 的路径。将这些小路径拼接在一起,我们得到 A 到 C 到 D 到 B。
在 Emil 给出的示例中,无论您使用哪种方式划分该矩阵,都无法获得有效的对来进行测试,因此您可以立即得出结论,不存在这样的路径。