Задачі
Найкоротший шлях коня
Найкоротший шлях коня
На шаховій дошці розміром 8×8 задано дві клітинки. З'єднайте ці клітинки найкоротшим шляхом коня.
Вхідні дані
Задано координати двох клітинок, кодна у окремому рядку. Координати клітинок задаються у вигляді букви (від "a" до "h") та цифри (від 1 до 8) без пропусків.
Вихідні дані
Вивести шлях коня, який починається і завершується у заданих клітинках і містить найменше число клітинок.
Приклад
Вхідні дані #1
a1 h8
Вихідні дані #1
a1 b3 c5 d7 e5 f7 h8