Znalezienie bloki w macierzach

Question

Szukałem na kilka pytań do wywiadu, i ja natknęliśmy się na ten jeden:

Jest tablicą m x n. Blok w tablicy jest oznaczony jako 1, a 0 oznacza brak bloku. Powinieneś znaleźć liczbę obiektów w tablicy. Obiekt to tylko zestaw bloków, które są połączone poziomo i/lub pionowo.

np

0 1 0 0 
0 1 0 0 
0 1 1 0 
0 0 0 0 
0 1 1 0 

Odpowiedź: Istnieją 2 obiektów w tej tablicy. Obiekt kształtu L i obiekt w ostatnim wierszu.

Mam problem z wymyśleniem algorytmu, który złapie kształt "u" (jak poniżej). Jak mam się do tego zbliżyć?

0 1 0 1 
0 1 0 1 
0 1 1 1 
0 0 0 0 
0 1 1 0 

Answer 1

ta działa w 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; 
    } 

Answer 2

Dlaczego nie wystarczy spojrzeć na wszystkie sąsiednie komórki danego bloku? Zacznij od pewnej komórki, w której znajduje się 1, śledź komórki, które odwiedziłeś wcześniej, i przeglądaj sąsiednie komórki, aż nie znajdziesz już 1. Następnie przejdź do komórek, na które jeszcze nie wyglądałeś i powtórz proces.

Answer 3

Coś jak to powinno działać:

1. gdy tablica ma wartość 1, który nie jest oznaczony:
   1. Utwórz nowy obiekt
   2. utworzyć kolejkę
   3. Dodać 1 do kolejki
   4. Podczas gdy kolejka nie jest pusta:
      1. dostać 1 na wierzch kolejki
      2. Mark to
      3. Dodaj go do bieżącego obiektu
      4. szukać swoich 4 sąsiadów
      5. , czy któryś z nich nie jest 1 i nie jest jeszcze zaznaczone, dodaj go do kolejki

Answer 4

Jedna z metod użyje Flood Fill. Algorytm będzie coś takiego:

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

Można by zaznaczyć elementy odwiedzonych podczas procesu napełniania przeciwpowodziowej, a także śledzić kształty stamtąd również.

Answer 5

Używałbym zestawów rozłącznych (podłączonych komponentów).

Na początku każdy element macierzy (i, j) o wartości 1 jest jednym zestawem elementów.

Następnie możesz powtórzyć każdy element macierzy i dla każdego elementu (i, j) powinieneś dołączyć do każdego sąsiedniego zestawu {{i + 1, j), (i-1, j), (i, j + 1), (i, j-1)} do (i, j), powołany jeśli jego wartość to 1.

można znaleźć implementację rozłącznych zbiorów w Disjoint Sets in Python

na koniec, liczby mówią jest zestawy to liczba obiektów.

Answer 6

chciałbym użyć disjoint-set datastructure (inaczej zwanego Unią znaleźć).

Krótko: dla każdego podłączonego komponentu zbuduj "drzewo odwrotne", używając pojedynczego łącza dla każdego elementu jako wskaźnika "rodzica". Podążanie za wskaźnikami rodzica ostatecznie odnajduje katalog główny drzewa, który jest używany do identyfikacji komponentów (ponieważ jest taki sam dla każdego elementu podłączonego komponentu). Aby scalić sąsiednie komponenty, należy uczynić pierwiastek jednego elementu rodzicem drugiego (który nie będzie już rootem, ponieważ ma teraz element nadrzędny).

Dwie proste optymalizacje sprawiają, że ta struktura danych jest bardzo wydajna. Jednym z nich jest, aby wszystkie zapytania root'a "zwijały" swoje ścieżki, aby wskazywały bezpośrednio na katalog główny - w ten sposób następne zapytanie będzie wymagało tylko jednego kroku. Drugi to: zawsze używaj "głębiej" dwóch drzew jako nowego korzenia; wymaga to utrzymania wyniku "rangi" dla każdego korzenia.

Ponadto, w celu zwiększenia wydajności sąsiadów, można rozważyć wstępne przetwarzanie danych wejściowych na podstawie rzędów po wierszu. W ten sposób ciągły segment 1 w tym samym wierszu może rozpocząć życie jako pojedynczy połączony komponent i można skutecznie skanować segmenty poprzedniego rzędu na podstawie kryterium sąsiada.

Answer 7

Moje dwa centy (ukośnik) Algorytm:

1. List only the 1's. 

2. Group (collect connected ones). 

W 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) 

wyjściowa:

*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)