Задача 9: Вирусы.
На поле размером n*n (n<=500) расположено m (1<=m<=10) вирусов. За
каждый ход вирус заражает 4 соседние с ним клетки. Положение вирусов
задано координатами на поле.
Определить, за какое наименьшее количество ходов будет заражено все
поле.
Решение:
Эта задача была на командном турнире среди школьников и студентов,
проводимом АО ICL КПО ВС, в Казани в 2000г.
Попробуем снова решить эту задачу. Рассмотрим возможность создания
массива, изображающего игровое поле, которые будут заполняться по
мере прохождения периода. Это приведет к необходимости сканирования
массива 500*500 каждый период и достаточно сложным операциям над
ним.
Представим, что у нас на поле один вирус и клетка с координатами X,
Y и нужно определить, за сколько ходов данная клетка будет заражена.
Это делается достаточно просто:
H = |X - I| + |Y - J| - где I, J - координаты вируса. Представим это
на рисунке:
6543456
5432345
4321234
321*123
4321234
5432345
6543456
Звездочкой обозначен вирус, а клетки хранят значение, через какое
время они будут заражены.
У нас есть формула, определяющая, через какое время конкретная
клетка будет заражена конкретным вирусом. Однако, у нас на поле
может быть несколько вирусов, так что нужно определить время
заражения клетки каждым вирусом, а итоговое время будет минимальным
из них.
Затем мы должны найти максимальное значение среди ранее просчитанных
минимальных количеств периодов необходимых для заражения клетки
(реально это надо считать динамически).
Далее
ð
