- Rook
Задача Rook. На
нескінченному аркуші в клітинку, у якому деякі клітинки можуть бути
вирізані, розміщено шахова тура. Рядки і стовпчики аркуша пронумеровано
по порядку цілими числами. Стовпчики пронумеровані зліва направо, а
рядки – знизу вверх. Тура одним ходом може переміщуватись на будь-яку
іншу невирізану клітинку, що знаходиться в одному рядку чи стовпчику з
початковою. Тура не може перестрибувати через вирізані клітинки. За яку
найменшу кількість ходів тура може перейти з одного вказаного поля на
інше (якщо це можливо)?
Технічні умови. Програма Rook читає з клавіатури чотири цілих числа x1, y1, x2, y2, розділені пропусками: x1 (номер стовпчика) і y1 (номер рядка) - координати клітинки, де тура знаходиться спочатку, а x2 (номер стовпчика) і y2 (номер рядка) - координати клітинки, куди тура повинна потрапити. Далі програма читає кількість вирізаних клітинок n (0<=n<=1000) і n пар цілих чисел x (номер стовпчика), y
(номер рядка) – координати вирізаних клітинок. Всі вирізані клітинки
різні, початкова і кінцева клітинки не вирізані, координати всіх
клітинок не перевищують за абсолютною величиною 1000000000. Програма виводить на екран шукану мінімальну кількість ходів тури або -1, якщо перейти неможливо.
Приклади
Введення
1 –1 5 -4 4 1 1 5 –5 2 –4 4 –1
Виведення
3
Введення
10 11 5001 -4733 5 5001 -4732 5001 –4734 1 1 5000 –4733 5002 –4733
Виведення
-1
