確定一個矩陣的週期

我有一個矩陣，每個單元格都有一個布爾屬性。我需要確定一個循環，從具有boolean屬性false的單元格開始，並且此循環必須只包含具有布爾屬性設置爲true的單元格（顯然除了起始單元格）。另一個條件是週期中的任何兩個連續單元必須位於同一行（或同一列）上，並且週期中的三個連續單元不得位於同一行（或同一列）上。實際上，您可以從一個單元格跳到另一個單元格，它們不必是鄰居，它們必須位於同一行或列中。謝謝。確定一個矩陣的週期

來源

2013-01-10 Cosmin

請在此設置中定義一個循環。 – alexraasch

一個循環將是一組單元格，數組中的第一個單元格將是起始單元格，其他所有單元格都必須遵守上述條件。細胞序列應以起始細胞結束。 – Cosmin

如果「循環中的任何兩個連續的單元格必須在同一行上」，則任何三個連續的單元格也必須在同一行中，違反了您的條件「循環中的三個連續單元格不得在同一行上」。可以說，A，B和C是三個連續的單元格。含義A和B是兩個連續的單元格，B和C是兩個連續的單元格。由第一個條件A和B在同一行，B和C在同一行。這顯然意味着A，B和C都在同一行。你現在所做的設置似乎是不可能的。你需要修改它。 – Spundun

更新：我錯過了不需要在兩個相鄰單元格之間移動 - 這會擴大每個步驟中可能移動的數量，但並不會真正改變總體思路。

最容易實現的可能是depth-first search - 你從起始單元格開始，看看所有可能的移動 - 除了第一步移動以外最多有三種可能的移動。對於每個可能的移動，您都會以同樣的方式遞歸執行，直到您再次到達起始單元或者沒有可能的移動。在後面的情況下，你追蹤一個動作，並嘗試下一個可能性，如果剩下一個。

您必須傳遞最後一步移動的方向以及遞歸調用，因爲此方向對於下一步移動無效。如果不允許多次訪問單元格，則還必須跟蹤訪問的單元格，並在追蹤時取消標記。如果允許多次訪問單元格，則必須跟蹤之前訪問單元格時爲了避免循環而離開單元格的方向。

使用breath-first search而不是深度優先搜索將避免嘗試長時間的路徑，這是以解決大量部分解決方案爲代價的無解決方案。 A* search可能是另一個加快速度的選項。

備註：可能是因爲您第一次訪問該單元格時可能會直接採取其他舉措，因此幾次訪問某個單元沒有價值。第一次進入單元格時不允許移動的例外是，但我不確定這樣的路徑是否可行。

來源

2013-01-10 20:23:16

您只需跟蹤每個節點一位 - 節點是否已到達列移動或行移動。所以你也可以通過加倍節點數來實現這一點，而鏈接只能移動從一個標記爲「按列移動到此處」的單元格移動到同一行中標記爲「按行移動」的單元格中，這可能允許您使用某種標準圖形算法進行循環檢測。 – mcdowella

Daniel和mcdowella謝謝。我明白了，我只需要弄清楚如何實現遞歸，這樣我就可以知道何時停止： - ？ – Cosmin

單個位真的夠嗎？無需區分分別從左，右，上，下進入？我的另一個想法是構建一個可能移動的有向圖，然後測試起始節點到起始節點的可達性。但是你需要每個單元有四個節點，因爲從入站方向的可能移動的依賴性，我認爲這可能是昂貴的方式。但是當再次考慮它時，它似乎比執行搜索便宜得多。 –

確定一個矩陣的週期

回答

相關問題