eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Найкоротший шлях коня

Найкоротший шлях коня

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

На шаховій дошці розміром 8×8 задано дві клітинки. З'єднайте ці клітинки найкоротшим шляхом коня.

Вхідні дані

Задано координати двох клітинок, кодна у окремому рядку. Координати клітинок задаються у вигляді букви (від "a" до "h") та цифри (від 1 до 8) без пропусків.

Вихідні дані

Вивести шлях коня, який починається і завершується у заданих клітинках і містить найменше число клітинок.

Приклад

Вхідні дані #1
a1
h8
Вихідні дані #1
a1
b3
c5
d7
e5
f7
h8