Задача  Cavalery

 

На шахівниці  розміром  NxM знаходиться коней в різних клітинках. Шахіст намагається зібрати  всіх коней в одну, відому йому клітинку. Знайти мінімальну кількість ходів, яку потрібно для цього зробити шахісту. Якщо задача не має розв’язку (а це буває тоді, коли хоча б 1 кінь не може дійти до заданої клітинки), повідомити про це. Мабуть, вам вже зрозуміло, що в одній клітинці може знаходитись одночасно скільки завгодно коней.


Технічні умови. 
Програма Cavalery читає з клавіатури розміри шахівниці N, M  (2 ≤ N, M ≤ 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

© LIKT 1998-2018