m-достижимость в графах

Question

Предположим, у вас есть лабиринт NxN с Рыцарем, Принцессой и Выходом.

Есть также злая ведьма, которая планирует блокировать M квадратов (поджечь их). Она подожжет все эти блоки до того, как Рыцарь сделает свой первый ход (они не делают чередующихся ходов).

Учитывая карту лабиринта и M, вы можете решить в O (N ^ 2), сможет ли Рыцарь добраться до принцессы, а затем выйти, для любого выбора блоков Ведьмой (имеется в виду - может ли Ведьма сделать выбор, который бы помешал Рыцарю и Принцессе сбежать)?

Answer 1

Эта проблема, по-видимому, эквивалентна определению, существует ли M + 1 отличные пути от рыцаря до принцессы и M + 1 отличные пути от принцессы до выхода. Если есть только M отличных пути от рыцаря до принцессы (или принцессы, чтобы выйти), ведьма может просто сжечь один квадрат с каждого пути, блокируя спасение (и, увы, любой шанс на долгую и счастливую жизнь) романтика между ними). ​​

Например, лабиринт в вашем вопросе имеет два разных пути от рыцаря до принцессы и два разных пути от принцессы до выхода. Таким образом, который может сжечь min(2, 2), чтобы предотвратить побег.

Количество различных путей между двумя точками можно найти с помощью алгоритма максимальный сетевой поток . Каждая ячейка в сетке является узлом в сети; два узла имеют ребро (емкостью 1), соединяющее их, если они смежные и оба белого цвета. Максимальный сетевой поток от одной точки к другой представляет количество различных путей между ними.

Алгоритм Форда Фулкерсона решит проблему сетевого потока за O(E * f) время, где E - это число ребер в сети (не более N^2), а f - это значение максимального сетевого потока. Поскольку максимальный сетевой поток составляет не более 4 (у рыцаря есть только четыре возможных направления для его первого хода), общая сложность становится равной O(2 * E * 4) = O(N^2), как и было запрошено.

Избегание использования узла более одного раза

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

Мы можем изменить потоковый график, чтобы избежать использования узлов более одного раза, предоставив каждой ячейке четыре входных ребра, один защитный ребро и четыре выходных ребра (каждый из которых имеет вес 1) следующим образом :

Выходной фронт одной ячейки соответствует входу другой. Теперь каждая ячейка может использоваться только для одного пути, поскольку защитный край может иметь только поток 1. Ячейки приемника и ячейки источника остаются неизменными. У нас все еще есть постоянное число ребер в ячейке, оставляя сложность алгоритма без изменений.