Анонс #197. Кратчайший путь двух коней

Задача: на шахматной доске 8×8 стоит два шахматных коня и для каждого из них задана клетка, в которую он должен попасть. Переведите каждого из двух коней в заданную конечную клетку за наименьшее суммарное число ходов.

Примечание: два коня не могут одновременно находиться в одной клетке, но могут ходить в любом порядке (не обязательно по очереди).

Входные данные:

• (x1, x2) - x1 - начальная позиция 1го коня, x2 - позиция, куда необходимо переместить 1го коня, 
• (y1, y2) - y1 - начальная позиция 2го коня, y2 - позиция, куда необходимо переместить 2го коня.

Вывод: последовательность ходов коней - (номер коня, ход)

Пример:

• 1й конь: (a1, c2)
• 2й конь: (c2, a1)

Output:

(1, b3)

(1, d4)

(2, a1)

(1, c2)