Проверка проходимости сетки

Question

Рассмотрите эту проблему:

Существует квадратная сетка, каждая из которых является проходной (1) или непроходимой (0). Во-первых, мы имеем просто связное пространство в сетке с непроходимой границы, как это:

Затем начать размещение непреодолимые препятствия различных размеров (например, 1х1, 2х2, ..) в проходимое пространство. После того, как каждое препятствие помещено, нам нужно проверить, все ли еще подключено оставшееся проходимое пространство (т. Е. Убедитесь, что мы не разделили проходимое пространство в двух или более отключенных пространствах). Плитки также соединены по диагонали.

Дело в том, что после каждого размещения препятствий каждая оставшаяся проходимая плитка имеет путь, соединяющий ее с КАЖДОЙ другой оставшейся проходимой плиткой.

Я знаю о возможности поиска путей между возможными отключенными точками, но я боюсь, что это может быть слишком неэффективным. Меня интересует как можно быстрее это тестирование.

Спасибо за помощь!

Answer 1

Реализовать алгоритм заполнения наводнений. В качестве побочного эффекта выполнения заполнения подсчитайте количество заполненных квадратов. После размещения ваших препятствий выполните еще один поток заливки, начиная с любого открытого квадрата, и сравните количество заполненных квадратов с исходным числом минус количество квадратов, помещенных в качестве препятствий. Если они не совпадают, вы отключили регионы.

Answer 2

Wikipedia says что это можно сделать в амортизированном времени O (| V |) с использованием структур данных с несвязанными наборами, где V - количество элементов в проходимом пространстве (второй абзац этого раздела). Цитируется в this paper.

Это та же самая асимптотическая сложность, что и Benjamin's answer, и ее, по-видимому, сложнее реализовать, поэтому я бы пошел с этим. :)