Примеры сведения к задачам поиска потока

Материал из Викиконспекты
Версия от 20:05, 14 декабря 2016; Sultazat (обсуждение | вклад) (Добавил описание задачи №1)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Пример №1

Задача:
Дано поле размером N * M, некоторые клетки поля закрашены. В одной из клеток поля стоит монстр, он умеет ходить только по незакрашенным клеткам (из текущей клетки он может пойти только в ту клетку, с которой имеет общую сторону). Какое минимальное количество клеток нужно закрасить, чтобы монстр не смог выбраться из поля?