是否有此穿越問題的解決方案？

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.

在由埃米爾給出的，不管你分區矩陣方式的例子中，你不能得到有效的對測試，讓您可以立即得出結論，不存在這樣的路徑。