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