Задача Toxins. У популярній настільній грі завдання полягає в тому, щоб провести фішку по певному маршруту. Поле є прямокутником, що складається з квадратних клітинок. Гравець може за один хід перейти в одну з чотирьох сусідніх по стороні клітинок, не виходячи при цьому за межі поля. Гравець починає свій шлях у будь-якій клітинці самого лівого стовпця і повинен потрапити до будь-якої клітинки самого правого стовпця ігрового поля.
Але окремі клітинки токсичні, їх розташування відоме. Вася з'ясував, що чим більша відстань від токсичної клітинки, тим безпечніший маршрут, відстань обраховується як кількість ходів клітинками токсичних клітинок до кожної клітинки маршруту. Допоможіть йому визначити, на яку мінімальну відстань доведеться підійти до токсичної клітинки, рухаючись найбезпечнішим маршрутом.
Технічні умови. Програма Toxins читає з пристрою стандартного введення першому рядку записано натуральні числа N та М (1 ≤ N,М ≤500) — кількість рядків та стовпців на ігровому полі, у другому рядку записано натуральне число К (1≤К≤500) — кількість токсичних клітинок. У наступних К рядок записані пари чисел Ri Ci (1≤ Ri ≤N, 1≤Ci≤ М) — координати токсичних клітинок (рядок, стовпець). Програма виводить на пристрій стандартного виведення мінімальну відстань, на яку доведеться наближатися до токсичної клітинки на безпечному маршруті.
Приклад
|
Введення |
Виведення |
Коментар |
|
10 10 4 2 2 5 3 5 9 8 8
|
3 |
Приклад одного з безпечних маршрутів показано на малюнку. Токсичні клітинки – чорні, клітинки маршруту – сірі. Мінімальна відстань між токсичною клітинкою та маршрутом – 3 ходи |
