Олимпиадный тренинг

Задача 33251. Один конь


Задача

Темы: Обход в ширину
На шахматной доске NxN в клетке (x1, y1) стоит голодный шахматный конь. Он хочет попасть в клетку (x2, y2), где растет вкусная шахматная трава. Какое наименьшее количество ходов он должен для этого сделать?
 
Входные данные: на вход программы поступает пять чисел: N, x1, y1, x2, y2 (\(5 <= N <= 20\), \(1 <= x_1,\ y_1,\ x_2,\ y_2 <= N\)).
Левая верхняя клетка доски имеет координаты (1, 1), правая нижняя - (N, N).
 
Выходные данные: выведите единственное число K - наименьшее необходимое число ходов коня. 
 

 

Примеры
Входные данные Выходные данные
1 5
1 1
3 2
1