遍歷二維數組中的每個單元格

Question

我不確定該稱呼此問題，但我確定它有一個名稱。否則，找到答案會更簡單。

給定一個如細胞的 「地圖」：

O - - - 
- X - - 
- X X - 
- - - - 

其中O =起始位置，X =障礙物和 - =未訪問。我想遍歷這個地圖（我將它存儲爲一個二維數組），並訪問儘可能多的單元格而不觸及訪問的單元格。

我的算法如下：

1. 如果我能去的權利，向右走。
2. 否則，如果我可以下去，下去。
3. 否則，如果我可以向左走，向左走。
4. 否則，如果我可以上去，上去。
5. 如果我堅持，原路返回並標記細胞「unvisitable」，並回到1.

所以兩個問題：

• 對於較大的地圖，障礙物的數量，以及他們被放置經常導致我的算法不能達到很多細胞。我已經嘗試了步驟1-4的不同順序（即，如果我可以等的話，總是會往上走的），但顯然取決於給定的地圖。
• 我不知道什麼時候停下來。如果我的算法達到「終點」，即我實際訪問過所有可能的單元格，它就不會停下來，只是回溯到開始。

所以我想我的問題是：有沒有更好的方法來實現這個，或者我該如何調整我目前的算法來解決這個問題？

Answer 1

有一個名稱：最長路徑問題：https://en.wikipedia.org/wiki/Longest_path_problem

在曲線圖的形式，使從無細胞到阻止細胞邊緣具有無限的重量和所有其他的具有1的重量（或一些其他常數）。沒有「效率」（在算法複雜度方面）解決了這個問題（如果你找到一個你會出名！）

爲了解決您的兩個問題：

1. 你是正確的，取決於障礙物，您將無法訪問某些廣場，但它也取決於出發點。許多廣場完全有可能無法到達;例如，圍繞起點可能存在完全的障礙，然後全部無法到達。

2. 對於您當前的算法，您可以停止當您回溯到開始廣場，然後沒有更多的移動。否則你的算法看起來正確。最後步驟1-4的順序不會有任何區別。爲了知道哪條路徑最長，您仍然必須嘗試所有路徑（使用此方法）。

編輯：我不知道我早先讀過它的時候是否理解了第5步;即使你卡住了（如果你在那個廣場上，那麼你訪問過它），但是周圍的廣場（除了你來自的那個廣場外），當前廣場不應該被標記爲無法訪問。只要不標記當前的方塊不可檢測，回溯算法應該找到正確的最長路徑。

Answer 2

你的算法不會因爲這樣的情況下工作：

O - - - 
X - - X 

，因爲你的算法會首先去所有的路權

O 1 2 3 
X - - X 

和標記回溯時擋住了右側的單元格，所以它永遠不會找到最佳的

O 1 4 5 
X 2 3 X 

---

你可以用通用的方式解決這個問題，將其視爲一個圖形問題，並簡單地應用任何最長路徑算法（通常是NP-hard），但我不確定你是否熟悉這種方法。

一個可能更簡單的來看待它的方式是這樣的：

• 跟蹤當前的位置和所有你帶到那裏的步驟。
• 對於每個位置，您最終都會嘗試按順序向右（R），向下（D），向左（L），向上（U）順序進入各個方向。
• 當您嘗試了某個位置的所有方向（即，您嘗試了U）後，通過執行您所做的最後一個步驟的反轉，退一步。

---

一個例子可能有所幫助。再次考慮同一個例子。我用C代表當前位置，＃代表訪問單元。我們跟蹤移動堆棧和回溯情況下的最後一步。

C - - - Stack: [] 
X - - X Backtracked move: - 

步驟正確

# C - - Stack: [R] 
X - - X Backtracked move: - 

步驟正確

# # C - Stack: [R, R] 
X - - X Backtracked move: - 

步驟正確

# # # C Stack: [R, R, R] 
X - - X Backtracked move: - 

嘗試右，下，左，後，發現你被卡住，回溯，即採取正確的反向（le英尺）

# # C - Stack: [R, R] 
X - - X Backtracked move: R 

最後一次回溯移動是正確的，所以現在嘗試下一步，即，下臺

# # # - Stack: [R, R, D] 
X - C X Backtracked move: - 

試試吧，試下來，一步離開

# # # - Stack: [R, R, D, L] 
X C# X Backtracked move: - 

再次卡住了，所以原路返回

# # # - Stack: [R, R, D] 
X - C X Backtracked move: L 

最後出爾反爾的舉動被留下，所以現在嘗試採取下一步行動，即嘗試。注意我們被卡住了，並且進一步回溯。

快進到第一個有趣的下一步：

# C - - Stack: [R] 
X - - X Backtracked move: R 

最後一個是正確的，那麼請繼續往下。

# # - - Stack: [R, D] 
X C - X Backtracked move: - 

你可能已經明白了吧，所以我只是快進一路：

# # # C Stack: [R, D, R, U, R] 
X # # X Backtracked move: - 

和回溯一路：

C - - - Stack: [] 
X - - X Backtracked move: R 

最後此舉是對，所以試着下，左，上。你完成了。

一路上你跟蹤你見過的最長的路徑，那就是你的答案。