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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(Пример №1)
Строка 14: Строка 14:
 
</table>}}
 
</table>}}
 
</includeonly>
 
</includeonly>
[[Файл:Monster.png]][[Файл:MonsterSolution.png]]
+
[[Файл:Monster.png]] [[Файл:MonsterSolution.png]]

Версия 22:31, 24 декабря 2016

Пример №1

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


Monster.png MonsterSolution.png