Задача Crystal
Юний хімік Ліза вирощує кристали. На прямокутну пластину з поживним середовищем вона капає зародковими кристалами, які згодом ростуть і заповнюють усю пластину. У зв'язку з постійним недосипанням та мікроскопічними розмірами пластини вкраплення виходять розкиданими випадково по пластині і інколи кристали розростаються досить довго. Ліза вирішила визначити, за який час пластина повністю покриється кристалами, якщо відомі її розміри і місця вкраплення. З підручника з координаційної хімії відомо, що за 1 хвилину кристал розростається на сусідні клітинки, з якими він має спільне ребро.
Технічні умови. Програма Crystal читає з клавіатури числа H та W - кількість рядків і стовпців пластини, K - кількість вкраплень, які зробила Ліза, після чого K пар чисел R та C - відповідно рядок і стовпець вкраплення. Усі числа цілі та задовольняють обмеженням:
1 <= H, W <= 500; 0 <= K <= 50; 1 <= R <= H; 1 <= C <= W. Програма виводить на екран єдине число - мінімальну кількість хвилин, через яку вся пластина буде покрита кристалами, а якщо це ніколи не відбудеться, то вивести - 1
|
Приклад 1 Введення |
Виведення |
|
7 7 2 3 3 7 5 |
6 |
|
Приклад 2 Введення |
Виведення |
|
40 20 3 2 8 1 18 27 5 |
28 |