位圖，檢查正交路徑是否關閉

給出了一個2d位數組。位圖，檢查正交路徑是否關閉

var map1 = [[0,0,0,0,0,0,0,0], 
      [0,0,0,0,1,0,0,0], 
      [0,0,1,1,1,1,1,0], 
      [0,0,1,0,0,0,1,0], 
      [0,0,1,1,0,0,1,0], 
      [0,0,1,0,0,0,1,0], 
      [0,0,1,1,1,1,1,0], 
      [0,0,0,0,0,0,0,0]];

我該如何編程檢查是否有一些「一」正在形成一個封閉的路徑？

http://jsfiddle.net/RvN3k/

兩個左位圖包含封閉路徑時，上一個是顯而易見的，下面的一個僅僅與沒有內部的閉合路徑。

右邊的兩個位圖不包含封閉路徑，在上例的一個比特是缺少，在下面的例子中的一個對角像素不計數，只有正交路徑。

來源

2013-02-05 astropanic

查找持有1單元格，然後從那裏上「氾濫」。通過這個我的意思是：使用第二個地圖，所有初始設置爲0.當遇到第一個地圖時，將第二個地圖中的單元格設置爲1.現在檢查所有相鄰單元格，將第二個地圖單元格設置爲1在原始地圖中也是1.一旦你嘗試設置一個已經爲1的單元格，你就知道你遇到了一個封閉的路徑;不要再檢查那個單元格，否則你會得到一個無限循環。

編輯：如果你想通過封閉通道連接到一個細胞的所有細胞的完整列表，伸出了「氾濫」給最初僅持有起始單元格的列表中添加你遇到的每一個細胞。如果在某個時候你沒有發現另一個淹沒的單元格，那麼就沒有封閉的路徑，你可以扔掉這個列表。根據是否要將鏈接的位圖中的小「存根」視爲路徑的一部分，您必須執行一些分支，爲每個分支引入新列表，並在它們相交時合併它們。

來源

2013-02-05 20:47:53

我有這個想法，但不是製造二次地圖，我會用一個列表，並保存在那裏找到「一」，當我發現一個重複的cordinates，道路被關閉。與你的方法類似，但我認爲更多的記憶友好。你對這種方法有什麼看法？ – astropanic

是的，你也可以做到這一點，確保使用的東西，可以讓你有效地檢查重複。 –

我已經分叉你的小提琴並添加了一個方法findCycle（）。

var fill = function(map, x, y) { 
    if (Math.min(x,y) >= 0 && Math.max(x,y) < mapSize && map[x][y] == 0) { 
     map[x][y] = -1; 
     for (var dx = -1; dx <=1; dx +=1) { 
      for (var dy=-1; dy<=1; dy += 1) { 
       fill(map, x+dx, y+dy); 
      } 
     } 
    } 
} 

function detect(map) { 
    for(var x = 0; x + 1 < mapSize; x++){ 
     for(var y = 0; y + 1 < mapSize; y++){ 
      if (map[x][y] == 0) { 
       map[x][y] = -2; 
       return; 
      } 
      else if (map[x][y]== 1 && map[x+1][y]==1 && map[x][y+1]== 1 && map[x+1][y+1]==1) { 
       map[x][y] = -2; 
       return; 
      } 
     } 
    } 
} 

function findCycle(mapData) { 
    for(var x = 0; x < mapSize; x++){ 
     for(var y = 0; y < mapSize; y++){ 
      if (mapData[x][y] == 0) { 
       fill(mapData, x, y); 
       detect(mapData); 
       return; 
      } 
     } 
    } 
}

找到第一個0.遞歸地用「-1」填充所有相鄰的0。然後搜索任何仍然存在0的，可能不是從最初的0.1（而在同一時間搜索四個「1」（紅色）的正方形方即可到達。

http://jsfiddle.net/bn6pa/1/

一個黑色的正方形在它找到一個週期內第一點被繪製

來源

2013-02-05 23:50:27

記下撥弄，應當填寫（屬於MapData，X，Y），不填（屬於MapData，0，0） –

如果你仍然在這之後，我希望能在小提琴[這裏]評論，最初由你的啓發。我認爲CPU的複雜性會好一些。 – Miquel

嗨米克爾。我不認爲複雜性會更快（我的是O（n））。不過，我使用遞歸，所以比使用while循環要慢。如果它在遞歸中下降太多，我也可以吹掉堆棧幀。隨着你的小提琴，我沒有時間看正確，但也許嘗試允許對角線移動（如果你還沒有）。 –

如何：。

for each cell that's set to 1 
    set that cell to -1 
    recursively look for neighbouring cells set to 1, and set them to -1 
     if you find a neighbouring cell that is already set to -1, loop found 
    clean-up (set all cells that are set to -1 to 0, they are no longer relevant)

這應該接近運行O（N）

在這裏，我已經實現了這個小提琴，檢查出來here。你會注意到第四個例子很奇怪：我還沒有找出結果，因爲你的問題定義並沒有說明你是否想要最大的循環或任何其他的循環。事實上，你只是想知道是否有一個循環，這是知道你點擊一個淺藍色像素的時刻。

來源

2013-02-06 22:06:54 Miquel

位圖，檢查正交路徑是否關閉

回答

相關問題