Изменения

Используя [[Схема алгоритма ДиницаАлгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|алгоритм ДиницаФорда-Фалкерсона]], найдём максимальный поток в сети. Согласно [[Теорема о декомпозиции|теореме о декомпозиции]], нахождение максимального потока эквивалентно тому, что мы нашли максимальное количество путей из истока в сток. Т.е. требуемый ответ на задачу равен максимальному потоку.  Время работы алгоритма Форда-Фалкерсона <tex>O(E|f|)</tex>. Заметим, что максимальный ответ равен 4, т.к. можно закрасить клетку слева, справа, сверху и снизу от позиции монстра, и он не сможет никуда двигаться, поэтому <tex>|f|</tex> можно считать константой. Итоговое время работы <tex>O(E)</tex>.