`Всеукраїнський центр проведення олімпіад в мережі Інтернет


Задача Bishop


На шаховiй дошцi розмiрами М*N клiтинок стоїть слон (фiгура, що ходить по дiагоналi). З'ясувати, чи може слон дiйти до поля (x,y) Якщо може, то за яку найменшу кiлькiсть ходiв; якщо кiлькiсть ходiв бiльша за 1, то 
вказати, через якi промiжнi клiтинки повинен пройти слон (якщо таких маршрутiв кiлька, вказати будь-який один з них). Поля шахової дошки кодуються парою натуральних чисел 1..М, 1..N, де перше число - номер 
горизонталi, а друге - номер вертикалi (1<=М,N<=1000).

Технiчнi умови: Ви вводите з клавiатури через пропуск числа М, N, а далi координати початкового та кiнцевого полiв бажаного маршруту слона. Ви виводите на екран число К (мiнiмальна кiлькiсть ходiв), а далi в К-1 рядках по 2 числа через пропуск - координати вiдвiданих полiв. Якщо розв'язкiв немає, вивести

Приклад: 

Введення                                                                                                                  Виведення
10 10 1 1 1 7                                                                                                             2
                                                                                                                                   4   4


Задача Bishop


На шахматной доске размерами М*N клеток стоит слон (фигура, которая ходит по диагонали). Выяснить, может ли слон дойти до поля (x,y). Если может, то за какое наименьшее количество ходов; если количество ходов больше 1, то указать, через какие промежуточные клетки должен пройти слон (если таких маршрутов несколько, указать любой из них). Поля шахматной доски кодируются парой натуральных чисел 1..М,1..N, где первое число - номер горизонтали, а второе - номер вертикали (1<=М,N<=1000).

Технические условия: Вы вводите с клавиатуры через пробел числа М, N, а далее координаты начального и конечного полей желаемого маршрута слона. Вы выводите на экран число К (минимальное количество ходов), а далее в К-1 строках по 2 числа через пробел - координаты посещенных полей. Если решений нет, вывести 0.

Пример: 

Ввод  Вывод
10 10 1 1 1 7  2
4  4

© LIKT 1998-2024