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


Годинник
 
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

 


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