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

Question

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

Определена квадратная сетка, каждая клетка либо проходима (1), либо непроходима (0). Сначала у нас есть просто связанное пространство в сетке с непроходимой границей, как это:

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

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

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

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

Answer 1

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

Answer 2

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

Это та же асимптотическая сложность, что и Ответ Бенджамина , и предположительно сложнее в реализации, поэтому я бы с этим согласился. :)