Подсчитайте количество связанных точек в сетке

Question

У меня есть сетка из m X n ячеек. Некоторые из них включены и выключены. Найдите эффективный алгоритм для подсчета количества соединений.

Многие точки, соединенные сверху, слева, справа и снизу, все еще считаются одним соединением.

Answer 1

Сканирование вашей сетки в некотором порядке. Когда вы достигнете ячейки, которая включена, выполните заливку на ней.

«Заполните» каждую ячейку, выключив ее. После завершения заливки продолжите сканирование.

Количество подключенных компонентов в исходной сетке равно количеству выполненных вами заливок.

Answer 2

Конечно, хорошей структурой данных для такого рода проблем (« определяет количество подключенных компонентов ») является структура данных UnionFind ; он дает почти линейный (по размеру сетки) алгоритм. Но оказывается, что для вашей конкретной задачи, которая напоминает упражнения в лабиринте, поставленные в задачах развлекательного программирования, существует более примитивное, даже лучшее (линейное) решение. 1006

Вы окрашиваете каждую подключенную область в другой цвет. Идея состоит в том, что для этого вам нужно только отслеживать, как вы покрасили последнюю обработанную линию сетки. Хитрость заключается в том, чтобы знать (а) какой цвет выбрать и (б) как подсчитать различные связанные области.

def countConnectedAreas(grid, n):
  vector = [0] * n    # Buffer vector containing current zones.
  count = 0           # Current number of connected areas.
  nextToken = 1       # Next color to use to paint a newly encountered zone.

  for line in grid:
    current = 0
    for i in range(n):
      if not line[i]:
        # Not dot.
        current = 0
      else:
        # There is a dot.
        if current != 0 and vector[i] != 0 and current != vector[i]:
          # This is the tricky case: it means you can paint the next
          # square with two colors, which means that two connected
          # areas are merging. Automatically, this means that you are
          # seeing one less connected area.
          count -= 1
        else:
          current = max(current, vector[i])
          if current == 0:
            # If the neighboring squares are colored 0, then pick a new
            # color.
            current = nextToken
            nextToken += 1
            count += 1

      vector[i] = current

  return count

Вот пара сеток, чтобы попробовать это на:

gridOne = [
  [ True, True, False, False, False, False, True ],
  [ True, True, False, False, False, False, True ],
  [ True, True, False, True, True, False, True ],
  [ True, True, False, False, True, False, True ],
  [ True, True, False, False, False, False, True ],
  [ False, True, False, False, False, False, True ],
  [ False, True, True, False, False, False, True ],
  [ True, False, True, False, False, False, True ] ]

gridTwo = gridOne + [
  [ True, True, True, True, True, True, True] ]

countConnectedAreas(gridOne, 7)    # returns 4
countConnectedAreas(gridTwo, 7)    # returns 2

Answer 3

Вы можете использовать алгоритм поиска в глубину .Этот алгоритм может найти количество связанных компонентов в любом неориентированном графе за время O (E), где E - количество ребер в графе.На сетке у вас есть O (nm) ребер, поскольку каждая вершина имеет не более четырех соседей.