Queen#618
На узагальненій шахівниці (не обов'язково 8 \times 8) розташована ферзь. Відомо, на якій клітинці вона знаходиться зараз і на яку клітину їй потрібно потрапити. Але задача ускладнюється тим, що частина клітин зайнята ворожими фігурами. Втім, усі ці фігури міцно сплять, і ферзь може рухатись скільки завгодно разів, головне — не розбудити їх. Ферзь не може перестрибувати або брати ці фігури, бо це їх розбудить.
Ваше завдання — написати програму, яка визначає мінімальну кількість ходів, необхідних ферзю, щоб потрапити на цільову клітину.
Програма зчитує з клавіатури розміри шахівниці: спочатку кількість вертикалей (2 \leq w \leq 26), потім кількість горизонталей (2 \leq h \leq 99). Далі йдуть координати початкової та кінцевої клітини, потім кількість ворожих фігур (0 \leq K \leq w \cdot h - 2). Після цього йде пар чисел — координати кожної ворожої фігури. Усі числа розділені пробілами. Координати всіх клітинок — натуральні числа, що не перевищують та відповідно. Спершу задається вертикальна координата, потім горизонтальна. Початкова і кінцева клітини не зайняті фігурами, і жодна клітина не містить більше однієї ворожої фігури.
Програма повинна вивести одне ціле число — мінімальну кількість ходів, необхідних ферзю, щоб потрапити з початкової клітини на кінцеву, або , якщо дістатись цільової клітини неможливо.
Приклад 1