У меня есть сетка с началом, концом и некоторыми стенами. Единицы занимают самый короткий путь (перемещение только вверх/вниз/влево/вправо) от начала до конца, не проходя через стены.
Пользователь может добавить столько дополнительных стенок, сколько захочет изменить путь.
Однако обратите внимание, что независимо от того, сколько стен добавлено или где они добавлены, есть некоторые квадраты, которые могут никогда быть частью кратчайшего пути!
Эти квадраты никогда не могут быть частью кратчайшего пути!
Я ищу способ определить, какие квадраты никогда не могут быть частью кратчайшего пути.
Вышеприведенные случаи достаточно легко найти; но есть более сложные случаи. Рассмотрим:
В приведенном выше изображении ни один из квадратов с красными точками никогда не может быть частью лучшего пути, потому что есть только один вход в эту область, и это всего лишь два пробела. Если бы это было три пространства в ширину, или если какая-либо одна из стен была удалена, большинство из этих квадратов могли бы быть частью наилучшего пути.
Я пытаюсь выяснить способ обнаружения таких случаев, как выше (в основном с использованием мини-разрезов и наводнений), но без успеха. Кто-нибудь знает, как решить эту проблему?