10364: Найкоротший шлях коня-2
Відправити розв'язок
Бали:
100 (partial)
Time limit:
1.0s
Memory limit:
64M
Author:
Problem type
Allowed languages
Brain****, C, C++, Java, Pascal, Python, v8js
На шаховій дошці розміром \(NxN\) в клітинці \((r1,c1)\) стоїть шаховий кінь. Визначіть за яку найменшу кількість ходів він може потрапити в клітинку \((r2,c2)\)
Формат вхідних даних
В першому число \(N\) - розміри дошки (\(5 \le N \le 20\)).
В другому рядку два числа \(r1,c1\) - рядок і стовпчик позиції коня
В третьому рядку два числа \(r2,c2\) - рядок і стовпчик фінішної позиції
Формат вихідних даних
В першому рядку виведіть довжину найкоротшого маршруту коня до фінішу (найменшу кількість ходів коня).
В наступних рядках виведіть по 2 числа (координати клітинок, які відвідував кінь на шляху від стартової до фінішної)
Якщо мінімальних шляхів є декілька - виведіть будь-який.
Приклад вхідних даних
5
3 3
5 1
Приклад вихідних даних
4
3 3
2 1
1 3
3 2
5 1
Коментарі