在網格中查找具有特定值的連接塊

Question

我無法找到用於解決問題的算法。

我有一個8x8塊的網格，每個塊的值範圍從0到9.我想找到匹配總值例如15的連接塊的集合。我的第一個方法是開始於邊界，工作得很好。但是當在網格中間開始時，我的算法會丟失。

有人會知道一個簡單的算法使用，或者你能指點我在正確的方向嗎？

謝謝！

Answer 1

據我所知，沒有簡單的算法存在。至於爲您指出正確的方向，8x8網格實際上只是圖的一個特例，所以我將從圖遍歷算法開始。我發現在這種情況下，有時可以幫助您考慮如何解決小網格問題（比如3x3或4x4），然後查看您的算法是否可以擴展到「全尺寸」。

編輯：
我提出的算法是修改後的深度優先遍歷。要使用它，您必須將網格轉換爲圖形。該圖應該是無向的，因爲連接的塊在兩個方向上均等地連接。

每個圖形節點代表一個單獨的塊，包含該塊的值和一個變量visited。邊權重代表了他們的邊緣抵抗被跟隨。通過總結它們連接的節點的值來設置它們。根據您所尋找的總和，您可以通過刪除保證失敗的邊來優化這一點。例如，如果您要查找15，則可以刪除權重爲16或更大的所有邊。

算法的其餘部分將執行與塊一樣多的次數，每個塊作爲起始塊一次。沿着當前節點的最低權重邊遍歷圖，除非這會將您帶到訪問節點。將每個訪問節點推入堆棧，並將其變量visited設置爲true。爲每條路徑保留一個運行總和。

• 每當達到所需的總和時，將當前路徑保存爲您的答案之一。不要停止遍歷，因爲當前節點可能連接到零。
• 每當總數超過期望的總和時，通過將visited設置爲false並將當前節點從堆棧彈出來回溯。
• 每當給定節點的所有邊都被探測過時，回溯。

從給定起始節點的每條可能路徑都經過分析後，每個包含該節點的答案都已找到。因此，刪除接觸起始節點的所有邊並選擇一個新的起始節點。

我還沒有完全分析這個算法的效率/運行時間，但是...它不好。 （考慮在包含全零的圖中要搜索的路徑的數量）。也就是說，它遠勝於純粹的強力。