1. Crystal

Задача Crystal

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

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

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