查找覆蓋所有檢查點的路徑

我有一個大小爲2*N的矩陣A數組，每個元素爲*檢查點或X危險點不允許進入危險點。查找覆蓋所有檢查點的路徑

您需要查找是否有exist a path覆蓋所有檢查點而不訪問危險點，並且每個點都是visited once。

你可以在任何檢查站開始你的旅程。

對於前：

*X** 
***X

路徑存在訪問所有的檢查站。

我的方法：

選擇第一檢查站從0遇到到N：

如果你在index i和其它陣列（A [0]或A [1]）包含了chekpoint所以如果可能的話，切換數組，如果不在相同的數組中繼續。

最後檢查是否訪問了所有檢查點。

我的做法是不給我正確的答案有什麼錯在這裏

代碼：

dfs(int x , int i){ 
    Visted[x][i] = true; 
    if(!Visted[x^1][i] && A[x^1][i] == '*') 
     dfs(i, x^1); 
    else if(i+1 < n && A[x][i] == '*') 
     dfs(i+1,x); 
}

來源

2017-05-28 Regression

目前還不完全清楚「每個點訪問過一次」。這是否應該是「每個觀察點不超過一次」？ –

@ n.m。也許它意味着「恰好一次」。 – Gassa

@ n.m。每個點應該只訪問一次 – Regression

正如你所看到的，一旦你選擇了初始點，通過你的算法解決方案或者是獨特的或者不存在，因爲它最多隻有一個步驟來嘗試每個單元格。

所以，問題可能出在你沒有顯示的部分：你如何選擇初始點？使用此算法，您可以嘗試這兩種情況，並查看是否有一個結果路徑覆蓋了每個單元格。

這裏有兩個例子。在左邊，我們必須從第一行開始。在右邊，我們必須從第二行開始。

*X 1X     ** 23 
** 23     *X 1X

來源

2017-05-28 08:48:36 Gassa

但我的'DFS'功能似乎是正確的？ – Regression

@JohnySins這可能是對的，但很難說沒有上下文。例如，什麼是x的範圍，什麼是n，座標從零開始還是從一開始，最初調用的函數如何。這是[完整的示例]（https://stackoverflow.com/help/mcve）將解決的問題。 – Gassa

我的算法在兩個測試用例上都是正確的。不知道什麼錯誤？ – Regression

查找覆蓋所有檢查點的路徑

回答

相關問題