是否有此穿越问题的解决方案？

Question

说我们已经给了两个随机指定exit和entrance矩阵M x N，

找到一个路径（上，下，左，右）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.

在由埃米尔给出的，不管你分区矩阵方式的例子中，你不能得到有效的对测试，让您可以立即得出结论，不存在这样的路径。