Олимпиады по программированию

olympiads.ru

Дистанционные семинары
Оглавление
Как пользоваться
Система проверки задач
Регистрация, изменение настроек
Страница сдачи решений
Результаты
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике

Дистанционные семинары
по подготовке к олимпиадам по информатике

Задача 05-2. Один конь

Имя входного файла input.txt
Имя выходного файла output.txt
Максимальное время работы на одном тесте: 3 секунд

На шахматной доске NxN в клетке (x1,y1) стоит голодный шахматный конь. Он хочет попасть в клетку (x2,y2), где растет вкусная шахматная трава. Какое наименьшее количество ходов он должен для этого сделать?

Формат входных данных
Входной файл содержит пять чисел: N,x1,y1,x2,y2(5 <= N <= 20, 1 <= x1,y1,x2,y2 <= N). Левая верхняя клетка доски имеет координаты (1,1), правая нижняя - (N,N).

Формат выходных данных
Первая строка выходного файла должна содержать единственное число K - наименьшее необходимое число ходов коня. В каждой из следующих K+1 строк должно быть записано 2 числа - координаты очередной клетки в пути коня.

Пример

input.txt output.txt
5
1 1
3 1
2
1 1
2 3
3 1