Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Crystal

Задача Crystal

Юный химик Лиза выращивает кристаллы.  На прямоугольную пластину с питательной средой она капает зародышевыми кристаллами, которые вскоре растут и заполняют всю пластину. В связи с постоянным недосыпанием и микроскопическими размерами пластины её вкрапления получаются разбросанными случайно по пластине и иногда кристаллы разрастаются достаточно долго. Лизе необходимо определить время, за которое пластина полностью покроется кристаллами, если известны ее размеры и места вкрапления. Из учебника по координационной химии известно, что за 1 минуту кристалл разрастается на соседние клеточки, с которыми он имеет общее ребро.

Технические условия. Программа Crystal читает с клавиатуры числа  H и W – количество строк и столбиков пластины, далее - число K – количество вкраплений, которые сделала Лиза, после чего K пар чисел  R и C – соответственно строка и столбик вкрапления. Все числа целые, разделены пробелами и удовлетворяют ограничениям: 1 <= H, W <= 500;  0 <= K <= 50; 1 <= R <= H; 1 <= C <= W.

Программа выводит на экран единственное целое число -  минимальное количество минут, после которого вся пластина будет покрыта кристаллами, а если этого никогда не случится, то вывести  -1.

Пример 1

Пример 2

Ввод

Вывод

Ввод

Вывод

7 7 2 3 3 7 5

6

40 20 3 2 8 1 18 27 5

28

  


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"