Как обнаружить квадраты на сетке, которые НИКОГДА не могут быть частью кратчайшего пути после добавления блоков?

У меня есть сетка с началом, концом и некоторыми стенами. Единицы занимают самый короткий путь (перемещение только вверх/вниз/влево/вправо) от начала до конца, не проходя через стены.

shortest path

Пользователь может добавить столько дополнительных стенок, сколько захочет изменить путь.

adding walls

Однако обратите внимание, что независимо от того, сколько стен добавлено или где они добавлены, есть некоторые квадраты, которые могут никогда быть частью кратчайшего пути!

These squares can never be part of the shortest path!
Эти квадраты никогда не могут быть частью кратчайшего пути!

Я ищу способ определить, какие квадраты никогда не могут быть частью кратчайшего пути.

Вышеприведенные случаи достаточно легко найти; но есть более сложные случаи. Рассмотрим:

None of the squares with red-dots can ever be part of the best-path

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

Я пытаюсь выяснить способ обнаружения таких случаев, как выше (в основном с использованием мини-разрезов и наводнений), но без успеха. Кто-нибудь знает, как решить эту проблему?

Ответы

Ответ 1

Рассмотрим любой путь от S до F. Этот путь может быть кратчайшим (если вы удаляете каждый другой квадрат), если вы не можете использовать "ярлыки", используя только те плитки. Это происходит только тогда, когда у вас есть два смежных квадрата, которые не смежны в пути. Поэтому вам нужно рассмотреть все пары смежных квадратов; все, что они отключают от S или F (без отключения S от F), не может быть частью кратчайшего пути. Кроме того, плитки, которые могут быть отключены одним квадратом, не могут быть частью какого-либо пути (который не повторяет вершин) от S до F, поэтому им тоже нужно идти.

Пусть N - число квадратов в сетке. Для любой конкретной пары квадратов (из них O (N)), то, что отключается, может быть вычислено в O (N) раз с наводнением, так что это O (N ^ 2). Это дешевле, чем min-cut, о чем вы говорили, пытаясь, поэтому я считаю его достаточно дешевым для вас.

Ответ 2

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

см. пример в вашем примере, это две желтые сетки, которые блокируют точки.

enter image description here

заблокированный одной сеткой, легко понять. При блокировке двумя:

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

Итак, вот алгоритм:

перечислить каждую пустую сетку

  • наденьте на него стену и используйте заливку заливом, чтобы найти заблокированные участки, они бесполезны.
  • попробуйте поместить стену на одну из них на четыре соседние сетки (если они пусты), используйте наводнение, чтобы найти заблокированные области, они бесполезны.