從所有起點解決迷宮

最近我遇到了一個問題，說：
假定迷宮具有字符*,.,C。 *代表牆壁，./C被允許。只有一個點標記爲C。現在給定一個殭屍站在任何允許點上，存在一系列命令（例如LDDRU或LLLRRDU等），使得如果殭屍程序從任何允許點開始，它至少通過C一次。
如：從所有起點解決迷宮

****** 
*.C..* 
**.*** 
*....* 
******

命令：RLLURUU

現在我知道如何解決使用DFS/BFS迷宮（最短路徑）。但任何人都可以提供一個關於如何處理這樣的問題的暗示嗎？
編輯：如果下一步是進入牆壁/外部迷宮，它將被忽略。和往常一樣L是左R是正確U IS UP D是關閉。

來源

2016-07-25 yobro97

最遠可以水平移動3步;例如; LLL，你只能在網格中的三個位置;在接下來的R之後，你可以在垂直走廊的三個位置;在UU之後，你肯定已經通過了C，所以一般來說：做出一些減少你可能位置的數量的動作，然後跟蹤你所有可能的機器人，並使每個動作通過C，通過使用「如果有牆，機器人不動」的規則。每當兩個可能的機器人結束在同一個方格中時，移除其中一個。 – m69

@ m69，謝謝你的回答。但更清楚的是，你可以使用給出的例子，並解釋你的邏輯到達答案....謝謝！ – yobro97

3行中有9個可能的位置;在LLL之後，任何機器人將位於其最左邊的位置，所以現在只有3個可能的位置;在另一個R之後，這3個機器人將位於第二左邊位置（垂直走廊）;在UU之後，它們都會在C上結束。 – m69

此問題與有限自動機的synchronizing words或復位序列的概念有關。你可以想象構建一個自動機，其中

每個開放空間加上C是一個狀態;
除C以外的每個狀態都會轉換到其自身，以確定每次碰到牆壁的移動;
除C之外的每個狀態在所指示的方向上轉換到相鄰的打開狀態，如果在該方向上存在開放點;和
C狀態在所有動作中轉變爲自己。

鑑於這個自動機，你現在正在尋找一個序列，每一個狀態到C狀態，因此連接到同步單詞。有許多用於查找同步字的算法，並且它們中的任何一個都可以適用於解決這個特定問題。一種選擇是build the power automaton from the original automaton並尋找從開始狀態到C狀態的路徑，我相信這最終會成爲關於將虛擬機器人合攏在一起的評論的理論最優版本（因爲它總是會找到最佳路徑）

來源

2016-07-25 03:31:17 templatetypedef

「構建功率自動機」 - 即使我們只構建可訪問的節點，它也是指數型的。更快嗎？我甚至不需要最短的同步字。 –

您鏈接到維基百科的移動版本。請修復。 –

@JanDvorak哦，對不起，我沒有意識到你不需要最短的解決方案。功率自動機的構造對於任意自動機來說是最壞情況指數，但我不確定這個機器人中的特定自動機是否會實際觸發它。我將不得不考慮那一個。還有其他的方法是已知的最壞情況下的多項式時間，儘管我不太熟悉它們。 – templatetypedef

從所有起點解決迷宮

回答

相關問題