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


Годинник
 
Newking
Задача Newking

Задача Newking

        На шахівниці розміром М*M стоїть білий король та P чорних пішаків. Пішаки ходити не можуть, а ось король ходить за шаховими правилами, але не може збивати пішаків. Чи зможе король дістатися до заданої клітинки? Якщо зможе, яку найменшу кількість ходів він при цьому повинен зробити?

        Технічні умови. Ви вводите з клавіатури число М (2<= M<=200) далі через пропуск число пішаків P , далі Р пар чисел – координати пішаків, далі 2 пари чисел – координати початкового положення короля і координати клітинки, в яку повинен прийти король. Ви виводите на екран єдине число: -1 , якщо дійти неможливо, або мінімальну кількість ходів, якщо маршрут існує.

Приклад 1.   Приклад 2.
Введення
4 2 3 1 3 4 1 1 4 3
Виведення
3
4     ?  
3 П     П
2        
1 К      
  1 2 3 4
 
Введення
4 2 3 1 3 3 1 1 4 3
Виведення
3
4     ?  
3 П   П  
2        
1 К      
  1 2 3 4

 


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