Как обнаружить связанные компоненты в 2D-массиве?

Как упоминалось в названии выше. Я хочу узнать, сколько компонентов в 2D-массиве. Принимая во внимание, что компоненты состоят из 1 чисел, а в массиве только 0 и 1 число. Я реализовал эту проблему с помощью алгоритма DFS (Deep First Search) с рекурсивными вызовами и массивом для отметки посещенных ячеек. Однако я хочу реализовать эту проблему другим способом, не используя рекурсию, стек, очередь, структуру... Разрешено только использование функции for/while.

Пример: данные массива:

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

Массив после определенных компонентов с определенными метками.

0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
0 0 2 2 2 0 3 3 0 1 0 0 0 0 0 1
0 0 2 0 2 0 3 3 0 1 0 4 4 4 0 1
0 0 2 0 2 0 0 0 0 1 0 4 0 4 0 1
0 0 2 0 2 0 0 0 0 1 0 4 0 4 0 1
0 0 2 2 2 0 0 0 0 1 0 4 0 4 0 1
0 0 0 0 0 5 5 5 0 1 0 4 4 4 0 1
0 0 0 0 0 5 0 5 0 1 0 0 0 0 0 1
0 0 0 0 0 5 5 5 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 6 6 6 6 6 0 0 0 0 7 7 7 7 0 0
0 6 0 0 0 6 0 0 0 0 7 0 0 7 0 0
0 6 0 6 6 6 6 6 0 0 7 7 7 7 0 0
0 6 0 6 0 6 0 6 0 0 7 7 7 7 0 0
0 6 6 6 6 6 6 6 0 0 0 0 0 0 0 0
0 6 6 6 6 6 6 6 0 0 0 0 0 0 0 0

Заранее спасибо.


arrays recursion multidimensional-array depth-first-search
person Long Uni    schedule 03.03.2014    source источник
comment
Будет лучше, если вы расскажете, почему вы это сделали и что уже пробовали.   -  person herohuyongtao    schedule 03.03.2014
comment
Связано: stackoverflow.com/questions/20844517/   -  person herohuyongtao    schedule 03.03.2014
comment
На самом деле, это моя домашняя работа, и я недавно говорил о программировании. Мой учитель не разрешает мне использовать что-то, что выходит за рамки урока в моем классе. Вот почему я использовал рекурсивную функцию в алгоритме DFS для этой проблемы, но это не принято. Использование стека, очереди, структуры также не допускается. Я могу использовать только цикл for/while, обычную функцию для этой проблемы. Надеюсь, вы сочувствуете!   -  person Long Uni    schedule 03.03.2014

Ответы (1)


arrow_upward
0
arrow_downward

Я думаю, вы могли бы перебрать матрицу и проверить соседей для каждой ячейки и скопировать значение соседа, если оно> 0, или установить новое значение, если все соседи равны 0. В псевдокоде:

comp = 1
for i = 0 to n:
  for j = 0 to n:
    for nei : neighbours(i, j):
      if nei > 0:
        m[i,j] = nei
        break
      m[i,j] = comp
      comp++

А соседями являются 4 (или 2) смежные соседние клетки с (i, j)

person QQQ    schedule 04.03.2014