Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Вирусы

(Время: 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.TXTOUTPUT.TXT
14 5
2 2 1 4 5
4

Пояснения

В приведённом примере таблица имеет размер 4*5, в ней символом ‘V’ помечены проникшие вирусы. Легко посчитать, что за четыре единицы времени произойдёт заражение всей области.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483, E-mail: admin@acmp.ru