Поиск блоков в массивах

Question

Я искал некоторые вопросы по собеседованию, и я наткнулся на этот вопрос:

Существует массив m x n. Блок в массиве обозначается символом 1, а 0 не указывает на какой-либо блок. Вы должны найти количество объектов в массиве. Объектом является не что иное, как набор блоков, которые связаны горизонтально и/или вертикально.

например

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

Ответ: Есть 2 объекта в этом массиве. Объект L-формы и объект в последней строке.

У меня возникли проблемы с алгоритмом, который поймал бы форму «u» (как показано ниже). Как я должен подходить к этому?

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

Answer 1

Это работает в 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

Почему бы не просто взглянуть на все смежные ячейки данного блока? Начните с некоторой ячейки, у которой есть 1 в ней, отслеживайте ранее посещаемые ячейки и продолжайте просматривать соседние ячейки, пока вы больше не сможете найти 1. Затем перейдите на ячейки, которые вы еще не просмотрели, и повторите этот процесс.

Answer 3

Что-то, как это должно работать:

1. в то время как массив имеет 1, который не отмечен:
   1. Создать новый объект
   2. Создание очереди
   3. Добавьте 1 к очереди
   4. Пока очередь не пуста:
      1. получить 1 в верхней части очереди
      2. Отмечать
      3. Добавьте его к текущему объекту
      4. взгляда своих 4 соседей
      5. , если любой из них является 1, а не отмечен еще, добавьте его в очередь

Answer 4

Один подход будет использовать 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 

Вы бы отметить элементы, посещенные в процессе заливки, а также отслеживать формы от там.

Answer 5

Я бы использовал непересекающиеся множества (связанные компоненты).

В начале каждого матричного элемента (i, j) со значением 1 устанавливается один элемент.

Затем вы можете выполнять итерацию по каждому элементу матрицы, и для каждого элемента (i, j) вы должны соединить каждое смежное положение set {(i + 1, j), (i-1, j), (i, j + 1), (I, J-1)} к (I, J), установленного, если его значение равно 1.

Вы можете найти реализацию непересекающихся множеств на Disjoint Sets in Python

в конце концов, количество diffrent sets - количество объектов.

Answer 6

Я бы использовать disjoint-set datastructure (иначе известный как союзная находка).

Коротко: для каждого подключенного компонента создайте «обратное дерево», используя одну ссылку на элемент в качестве «родительского» указателя. Вслед за родительскими указателями в конечном итоге будет найден корень дерева, который используется для идентификации компонента (поскольку он одинаковый для каждого члена подключенного компонента). Чтобы объединить соседние компоненты, сделайте корень одного компонента родителем другого (который больше не будет корнем, так как теперь он имеет родителя).

Две простые оптимизации делают эту структуру данных очень эффективной. Во-первых, все корневые запросы «сворачивают» их пути, указывая прямо на корень - таким образом, следующий запрос будет нужен только одному шагу. Другой - всегда использовать «глубже» двух деревьев в качестве нового корня; для этого требуется поддерживать оценку «ранг» для каждого корня.

Кроме того, чтобы сделать оценку соседей более эффективной, вы можете подумать о предварительной обработке ввода в строке за строкой. Таким образом, смежный сегмент 1 в одной строке может начать работу как один подключенный компонент, и вы можете эффективно сканировать сегменты предыдущей строки на основе критерия соседа.

Answer 7

Мои два цента (слэш) алгоритм:

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)