在數組中查找塊

我正在查看一些面試問題，並且我偶然發現了這一個：在數組中查找塊

有一個m×n數組。數組中的塊用1表示，而0表示無塊。你應該找到數組中的對象的數量。一個對象只不過是一組水平和/或垂直連接的塊。

例如

答案：有此陣列中的2個對象。 L形對象和最後一行中的對象。

我有麻煩想出一個算法，可以捕捉'u'（如下）形狀。我應該如何處理這個問題？

來源

2013-05-01 Lg102

你或許可以使用[顏色填充]（HTTP：// en.wikipedia.org/wiki/Flood_fill）查找形狀。掃描（未訪問）1並在您找到它時填充該形狀。 – thegrinner 2013-05-01 20:57:53

所以對角線不被認爲是有效的連接？ – 2013-05-01 21:39:41

不，他們不是。 – Lg102 2013-05-01 21:42:46

這個工作在C＃

static void Main() 
    { 
     int[][] array = { new int[] { 0, 1, 0, 1 }, new int[] { 0, 1, 0, 1 }, new int[] { 0, 1, 1, 1 }, new int[] { 0, 0, 0, 0 }, new int[] { 0, 1, 1, 0 } }; 
     Console.WriteLine(GetNumber(array)); 
     Console.ReadKey(); 
    } 

    static int GetNumber(int[][] array) 
    { 
     int objects = 0; 
     for (int i = 0; i < array.Length; i++) 
      for (int j = 0; j < array[i].Length; j++) 
       if (ClearObjects(array, i, j)) 
        objects++; 
     return objects; 
    } 

    static bool ClearObjects(int[][] array, int x, int y) 
    { 
     if (x < 0 || y < 0 || x >= array.Length || y >= array[x].Length) return false; 
     if (array[x][y] == 1) 
     { 
      array[x][y] = 0; 
      ClearObjects(array, x - 1, y); 
      ClearObjects(array, x + 1, y); 
      ClearObjects(array, x, y - 1); 
      ClearObjects(array, x, y + 1); 
      return true; 
     } 
     return false; 
    }

來源

2013-05-01 21:06:02

這不斷循環，但我不知道爲什麼。 – Lg102 2013-05-01 21:37:48

@ Lg102我繼續測試它的真實性，該錯誤可能在for循環中，他們都在做我++>< – 2013-05-01 21:46:24

Jep，我也只是接觸到了那個。我已經運行了上述代碼的改編，並且效果很好。謝謝。 – Lg102 2013-05-01 21:53:10

爲什麼不只是看看給定塊的所有相鄰單元？從其中有1個單元的單元開始，跟蹤之前訪問的單元，並繼續查看相鄰單元，直到找不到1爲止。然後轉移到尚未查看的單元格上並重復該過程。

來源

2013-05-01 21:00:08 Calpis

像這樣的東西應該工作：

而陣列具有不是標誌着一個1：
1. 創建一個新的對象
2. 創建隊列
3. 1添加到隊列
4. 雖然隊列不爲空：
  1. 獲得隊列頂部的1
  2. 將其標記
  3. 將它添加到當前對象
  4. 尋找它的4個相鄰
  5. 如果其中任何一個1和未標示的是，將其添加到隊列

來源

2013-05-01 21:01:45 iluxa

一種方法將使用Flood Fill。該算法是這樣的：

for row in block_array: 
    for block in row: 
     if BLOCK IS A ONE and BLOCK NOT VISITED: 
      FLOOD_FILL starting from BLOCK

你會紀念在洪水填充工藝參觀項目，並從那裏以及跟蹤形狀。

來源

2013-05-01 21:02:01 thegrinner

該算法的運行時間是什麼？ – 2013-10-29 04:42:34

@ Myth17我發佈的不太安全的洪水填充將是'O（mn）'。我不確定實際的洪水填充情況 - 它顯然取決於底層的實現，並且有一些聰明的事情可以改進。 – thegrinner 2013-10-29 14:13:01

我會使用不相交集（連接組件）。

開始時，值爲1的每個（i，j）矩陣元素都是一個元素集合。（i + 1，j），（i-1，j），（i，j + 1），則可以迭代每個矩陣元素併爲每個元素1），（I，J-1）}，以（I，J）設定其值爲1。

，可以看到在Disjoint Sets in Python

不相交的集合的執行在結束時，不同勢的數集合是對象的數量。

來源

2013-05-01 21:04:54

我會用一個disjoint-set datastructure（也稱爲合併 - 查找）。

簡而言之：對於每個連接的組件，使用每個元素的單個鏈接作爲「父」指針構建「反向樹」。在父指針之後最終將找到用於組件識別的樹的根（因爲它對連接組件的每個成員都是相同的）。要合併相鄰組件，請將一個組件的根目錄作爲另一個組件的父目錄（不再是根目錄，因爲它現在有一個父目錄）。

兩個簡單的優化使該數據結構非常有效。一個是，讓所有的根查詢「崩潰」他們的路徑直接指向根 - 這樣，下一個查詢將只需要一個步驟。另一種是，總是使用兩棵樹的「更深」作爲新的根;這需要維護每個根的「排名」分數。

此外，爲了使評估鄰居更有效率，您可以考慮逐行對輸入進行預處理。這樣，同一行上的連續段1可以作爲單個連接組件開始生命，並且可以根據鄰居標準有效掃描上一行的段。

來源

2013-05-01 22:02:28 comingstorm

我的兩分錢（斜線）算法：

1. List only the 1's. 

2. Group (collect connected ones).

在Haskell：

import Data.List (elemIndices, delete) 

example1 = 
    [[0,1,0,0] 
    ,[0,1,0,0] 
    ,[0,1,1,0] 
    ,[0,0,0,0] 
    ,[0,1,1,0]] 

example2 = 
    [[0,1,0,1] 
    ,[0,1,0,1] 
    ,[0,1,1,1] 
    ,[0,0,0,0] 
    ,[0,1,1,0]] 

objects a ws = solve (mapIndexes a) [] where 
    mapIndexes s = 
    concatMap (\(y,xs)-> map (\x->(y,x)) xs) $ zip [0..] (map (elemIndices s) ws) 
    areConnected (y,x) (y',x') = 
    (y == y' && abs (x-x') == 1) || (x == x' && abs (y-y') == 1) 
    solve []  r = r 
    solve (x:xs) r = 
    let r' = solve' xs [x] 
    in solve (foldr delete xs r') (r':r) 
    solve' vs r = 
    let ys = filter (\y -> any (areConnected y) r) vs 
    in if null ys then r else solve' (foldr delete vs ys) (ys ++ r)

輸出：

*Main> objects 1 example1 
[[(4,2),(4,1)],[(2,2),(2,1),(1,1),(0,1)]] 
(0.01 secs, 1085360 bytes) 

*Main> objects 1 example2 
[[(4,2),(4,1)],[(0,3),(1,3),(2,3),(2,2),(2,1),(1,1),(0,1)]] 
(0.01 secs, 1613356 bytes)

來源

2013-05-02 04:22:47

沒有解釋的downvote只是意味着什麼。 – 2016-07-16 13:52:09

在數組中查找塊

回答

相關問題