Задача g6_1010: Вирусы.

На поле размером n*n (n<=500) расположено m (1<=m<=10) вирусов. За каждый ход вирус заражает 4 соседние с ним клетки. Положение вирусов задано координатами на поле.
Определить, за какое наименьшее количество ходов будет заражено все поле.

Решение g6_1010:
Ура! У нас маленький юбилей - 10-я разобранная задача.
Эта задача встретилась мне на командном турнире среди школьников и студентов, проводимом АО ICL КПО ВС, в Казани в 2000г.
Попробуем снова решить эту задачу. Рассмотрим возможность создания массива, изображающего игровое поле, которые будут заполняться по мере прохождения периода. Это приведет к необходимости сканирования массива 500*500 каждый период и достаточно сложным операциям над ним.
Представим, что у нас на поле один вирус и клетка с координатами X, Y и нужно определить, за сколько ходов данная клетка будет заражена. Это делается достаточно просто:
H = |X - I| + |Y - J| - где I, J - координаты вируса. Представим это на рисунке:

6543456
5432345
4321234
321*123
4321234
5432345
6543456

Звездочкой обозначен вирус, а клетки хранят значение, через какое время они будут заражены.
У нас есть формула, определяющая, через какое время конкретная клетка будет заражена конкретным вирусом. Однако, у нас на поле может быть несколько вирусов, так что нужно определить время заражения клетки каждым вирусом, а итоговое время будет минимальным из них.
Затем мы должны найти максимальное значение среди ранее просчитанных минимальных количеств периодов необходимых для заражения клетки (реально это надо считать динамически).