Вирусы
(Время: 2 сек. Память: 16 Мб Сложность: 30%)
Для моделирования различных объектов часто применяются так называемые клеточные поля. В простейшем случае – это прямоугольные таблицы, характеризующие некоторую область, а в каждой ячейке таблицы записывается какая-либо информация об исследуемом объекте. В биологии для моделирования распространения вирусов на плоской области в каждой ячейке помечается наличие вируса, а его распространение осуществляется в соседние ячейки по вертикали и горизонтали за одну единицу времени. В начальный момент времени в исследуемую область проникли несколько вирусов. Напишите программу, которая найдёт время заражения всей исследуемой прямоугольной области.
Входные данные
Первая строка входного файла INPUT.TXT содержит два натуральных числа n и m - размеры таблицы (количество строк и столбцов соответственно). Известно, что 1 ≤ n, m ≤ 3000. Во второй строке вначале записано одно число k – количество проникших вирусов, а далее записаны 2k чисел – номера строк и столбцов первых заражённых ячеек yi, xi (1 ≤ k ≤ 10, 1 ≤ yi ≤ n, 1 ≤ xi ≤ m).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – время заражения всей области.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4 5
2 2 1 4 5 | 4 |
Пояснения
В приведённом примере таблица имеет размер 4*5, в ней символом ‘V’ помечены проникшие вирусы. Легко посчитать, что за четыре единицы времени произойдёт заражение всей области.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
