|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 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 |