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


Годинник
 
Cavalery
Задача  Cavalery


На шахівниці  розміром  NxM знаходиться Q коней в різних клітинках. Шахіст намагається зібрати  всіх коней в одну, відому йому клітинку. Знайти мінімальну кількість ходів, яку потрібно для цього зробити шахісту. Якщо задача не має розв’язку (а це буває тоді, коли хоча б 1 кінь не може дійти до заданої клітинки), повідомити про це. Мабуть, вам вже зрозуміло, що в одній клітинці може знаходитись одночасно скільки завгодно коней.
Технічні умови:
Програма Cavalery читає з клавіатури розміри шахівниці N, M  (2 ≤ NM ≤ 100), координати клітинки, де коні повинні зібратися, S, T (номер рядка та стовпчика), кількість коней Q (0 ≤ Q ≤ 10000), потім Q  пар чисел – координати кожного коня. Програма виводить на екран  одне число – мінімальну кількість ходів, або, якщо задача не має розв’язку,   кількість коней, що не можуть дійти до заданої клітинки.

Приклад :

Введення 4 4 1 1 3 2 3 3 2 3 3
Виведення 6
Введення 5 5 3 4 0
Виведення 0

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