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

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

Версия 23:48, 24 декабря 2016

Пример №1

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


Пример поля
Решение текущего примера

Во-первых, выбраться за пределы поля эквивалентно тому, что монстр может дойти по какой-либо крайней клетки. Во-вторых, заметим, что максимальное количество клеток, которые нужно закрасить, равно 4, т.к. можно закрасить клетку справа, слева, снизу и сверху от изначальной позиции монстра, чтобы он не смог никуда двигаться.

Покажем то, что минимальное количество клеток, которое нужно закрасить, равно максимальному количеству клеточно-непересекающихся путей из позиции монстра до крайних клеток поля