50
правок
Изменения
м
Во-первыхСразу скажем, что выбраться за пределы поля эквивалентно тому, что монстр может дойти до какой-либо крайней клетки. Во-вторых, заметим, что максимальное количество клеток, которые нужно закрасить, равно 4, т.к. можно закрасить клетку справа, слева, снизу и сверху от изначальной позиции монстра, чтобы он не смог никуда двигаться.
→Пример №1
</includeonly>
[[Файл:Monster.png|right|Пример поля]] [[Файл:MonsterSolution.png|right|Решение текущего примера]]
Покажем то, что минимальное количество клеток, которое нужно закрасить, равно максимальному количеству клеточно-непересекающихся путей из позиции монстра до крайних клеток поля. Очевидно, что ответ не больше, чем количество всех путей от монстра до крайних клеток. Сделаем ещё более строгое неравенство: ответ не больше, чем максимальное количество клеточно-непересекающихся путей, т.к. если мы возьмём какие-нибудь 2 пересекающихся пути и закрасим клетку в позиции, где они пересекаются, то мы блокируем путь монстру сразу по 2 этим путям. С другой стороны, если мы закрасим клетку на каком-то из путей, то у нас блокируется только этот путь, т.к. мы взяли клеточно-непересекающиеся пути. Значит, ответ не меньше, чем количество таких путей. В итоге получаем то, что и хотели доказать.
