e-olymp
Задачі

Переміщення коня

Переміщення коня

prb2820 Ваш друг проводить наукові дослідження з проблеми Конячої Мінімальної Подорожі (КМП), яка полягає у тому, щоб знайти найкоротший замкнений тур ходів конем, який відвідує кожну клітинку заданого набору з n клітинок на шаховій дошці рівно один раз. Він вважає, що сама важка частина задачі полягає у визначенні найменшої кількості ходів для переміщення коня між двома заданими клітинками і що, як тільки ви допоможете йому розв'язати цю підзадачу, то йому розв'язати усю задачу буде набагато легше.

Ви, звичайно ж, знаєте, що усе насправді як раз навпаки. Таким чином, ви у свою чергу вирішили самі запропонувати йому написати програму, яка розв'язує "важку" частину.

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

Вхідні дані

Вхідні дані будуть містити один або більше тестів. Кожен тест складається з одного рядка, який містить координати двох клітинок, відокремлені одним пропуском. Координати клітинки є двома символами, перший з яких літера (a-h), що задає стовбець, а другий – цифра (1-8), що задає рядок на шаховій дошці.

Вихідні дані

Для кожного тесту вивести один рядок наступного змісту: "To get from xx to yy takes n knight moves." (див. приклад вихідних даних).

Пример входных данныхПример выходных данных
e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6
To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Джерело II етап Всеукраїнсьої олімпіади школярів 2012-2013, м. Бердичів