簡單遞歸算法中終止路徑的問題

首先：這不是一項家庭作業，它是我的一個愛好項目。簡單遞歸算法中終止路徑的問題

背景： 對於我的Java益智遊戲，我用一個很簡單的遞歸算法，如果一定空間，以檢查的「地圖」已經成爲孤立的一塊放置後。在這種情況下分離的意思是：在沒有片可以放置在

當前算法：

public int isolatedSpace(Tile currentTile, int currentSpace){ 
     if(currentTile != null){ 
      if(currentTile.isOpen()){ 
       currentTile.flag(); // mark as visited 
       currentSpace += 1; 
       currentSpace = isolatedSpace(currentTile.rightNeighbor(),currentSpace); 
       currentSpace = isolatedSpace(currentTile.underNeighbor(),currentSpace); 
       currentSpace = isolatedSpace(currentTile.leftNeighbor(),currentSpace); 
       currentSpace = isolatedSpace(currentTile.upperNeighbor(),currentSpace); 
       if(currentSpace < 3){currentTile.markAsIsolated();} // <-- the problem 
      } 
     } 
     return currentSpace; 
    }

這段代碼返回空空間，其中起始瓦是其一部分的尺寸。這部分代碼的工作原理如圖所示。但是我碰到關於瓷磚的標誌，這是什麼使有關這個問題的標題一個問題就來了;）

問題： 的問題是，某些瓷磚從未「重新」（他們返回值和終止，所以從未從後來的化身中獲得返回值來更新空白空間的大小）。這些「被遺忘」的瓷磚可以是大空間的一部分，但仍然被標記爲孤立的，因爲在當前空間具有較低值時在開始處訪問它們。

問題： 如何改善這段代碼，使它爲瓷磚設置正確的值，而沒有太多的開銷？我可以想到醜陋的解決方案，如重新訪問所有標記的瓦片，以及它們是否具有適當的值，檢查鄰居是否具有相同的值，如果不更新等。但我確信有堆棧溢出的人們有更好的想法; ）

更新： 我已經做了一些改動。

public int isolatedSpace(Tile currentTile, int currentSpace, LinkedList<Tile> visitedTiles){ 
     if(currentTile != null){ 
      if(currentTile.isOpen()){ 
       // do the same as before 
       visitedTiles.add(); 
      } 
     } 
     return currentSpace; 
    }

而且marktiles功能（僅調用時返回spacesize比給定值小）

marktiles(visitedTiles){ 
     for(Tile t : visitedTiles){ 
      t.markAsIsolated(); 
     } 
}

這種做法與雷克斯克爾的答案線，至少如果我明白了他的理念。

來源

2010-08-19 Erik1984

另一方面，我想指出的是，根據所涉及的特定部分，即使大面積的形狀不佳，也可能是「孤立的」。例如，如果您沒有線性部分，則無法填充20個空格的線。如果那麼重要，你可能不得不下放試圖將每件作品放在每個位置/方向;標記任何有效位置覆蓋的方塊，然後完成標記反轉以獲得無用空間。 – 2010-08-20 15:44:56

您需要分兩步：收集有關空間是否隔離的信息，然後分別標記爲隔離。因此，您需要先計算所有空格（使用一個遞歸函數），然後標記所有連接的空格（如果標準通過）（使用不同的遞歸函數）。

來源

2010-08-20 13:57:22

感謝您的解決方案！你所描述的看起來就像我在此期間實施的一樣。每個標記的圖塊現在都被添加到名爲visitedTiles的列表中。在計算空間（並且最終大小已知）之後，稱爲markTiles的第二個函數（僅當空間的總大小小於某個值時）會將列出的圖塊標記爲孤立。這似乎工作正常。 – Erik1984 2010-08-20 15:10:19

這不是一個通用的解決方案，但是如果它們出現在兩個或更少空間的區域中，則只能將空間標記爲孤立。難道你不能簡化這個測試：「一個空間是孤立的，如果（a）它沒有開放的鄰居或者（b）恰好一個開放的鄰居並且那個鄰居沒有其他開放的鄰居」。

來源

2010-08-19 23:50:20 Rafe

這是個好主意，謝謝！然而，孤立空間的大小將隨着拼圖中使用的棋子而改變。碎片的形狀各異，有三種尺寸：三塊，四塊，五塊。因此，小於3塊瓷磚的空間總是被隔離，但是當僅有四塊或五塊塊可用時，小於4塊瓷磚也成爲隔離空間。 – Erik1984 2010-08-20 08:05:08

我認爲可能是這種情況。這裏有一個想法可能會讓你的算法更加精簡：爲每個空間添加一個「空間ID」字段。當您放置或移除一塊時，爲該空間選擇一個新的，新鮮的ID，並執行遞歸填充算法，用新ID標記每個連接的空間並跟蹤已標記的空間數量。如果你的空間ID有足夠的位（一個int很可能是好的，一個long可能是矯枉過正的），你不需要保留一個單獨的訪問過的tile的列表或者做一個單獨的標記階段。 – Rafe 2010-08-23 03:10:13

簡單遞歸算法中終止路徑的問題

回答

相關問題