Изменения

== Монстр и лабиринт Лабиринт Минотавра ==

|definition = Дано поле размером <tex>N \times M</tex>, некоторые клетки поля закрашены. В одной из незакрашенных клеток поля стоит монстрМинотавр, он умеет ходить только по незакрашенным клеткам (из текущей клетки он может пойти только в ту клетку, с которой имеет общую сторону). Какое минимальное количество клеток нужно закрасить, чтобы монстр Минотавр не смог выбраться за пределы поля?

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

Покажем то, что минимальное количество клеток, которое нужно закрасить, равно максимальному количеству клеточно-непересекающихся путей из позиции монстра Минотавра до крайних клеток поля. Очевидно, что ответ не больше, чем количество всех путей от монстра Минотавра до крайних клеток. Сделаем ещё более строгое неравенство: ответ не больше, чем максимальное количество клеточно-непересекающихся путей, т.к. если взять какие-нибудь 2 пересекающихся пути и закрасить клетку в позиции, где они пересекаются, то блокируется выход за пределы поля сразу по 2 этим путям. С другой стороны, если закрасить клетку на каком-то из путей, то блокируется только этот путь, т.к. были взяты клеточно-непересекающиеся пути. Значит, ответ не меньше, чем количество таких путей. В итоге получаем то, что и хотели доказать.

Рассмотрим [[Определение сети, потока#flow_network|сеть]], в которой вершинам будут соответствовать незакрашенные клетки поля, соседние незакрашенные клетки соединим ориентированными рёбрами с пропускной способностью 1. В качестве истока возьмём вершину, которой соответствует клетка монстраМинотавр. Добавим в граф ещё одну вершину — сток, добавим рёбра из вершин, соответствующим крайним клеткам поля, в сток с пропускной способностью 1. Чтобы пути не пересекались по клеткам, раздвоим каждую вершину графа на 2 вершины: в одну будут только входить рёбра, из другой — только выходить рёбра, и сами эти вершины соединим ребром с пропускной способностью 1.

Время работы алгоритма Форда-Фалкерсона <tex>O(E|f|)</tex>. Первое замечание: <tex>E</tex> <tex>\leqslant</tex> <tex>4V</tex> <tex>\leqslant</tex> <tex>4NM</tex> (это следует из того, что из каждой вершины исходит не более 4 рёбер), т.е. <tex>E=O(NM)</tex>. Второе замечание: ответ не превосходит 4, т.к. можно закрасить клетку слева, справа, сверху и снизу от позиции монстра Минотавра и он не сможет никуда двигаться, поэтому <tex>|f|</tex> можно считать константой. Итоговое время работы <tex>O(NM)</tex>.