Задача 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 |