Давным давно, Король Артур и Рыцари Круглого Стола собирались на Новый Год, чтобы отпраздновать свою дружбу. В память об этих событиях рассмотрим настольную игру Камелот для одного игрока, в которой фигура Короля и несколько фигур Рыцарей произвольно расположены в различных клетках доски.
Доска имеет размер 8х8 клеток (рис.1).
Рис. 1. Доска
Король может перемещаться в любую смежную клетку доски, как показано на рис.2, если при этом он не выходит за пределы доски.
Рис. 2. Все возможные перемещения Короля
Рыцарь может перемещаться так, как показано на рис.3, если при этом он не выходит за пределы доски.
Рис. 3. Все возможные перемещения Рыцаря
Во время игры игрок может поместить более одной фигуры в одну клетку. Клетки считаются достаточно большими и не возникает препятствий для свободного перемещения фигур.
Игроку необходимо так перемещать фигуры Короля и Рыцарей, чтобы собрать их в одной клетке за наименьшее число ходов. Ходы фигурами необходимо делать по правилам, описанным выше. Дополнительно, если Король и один или более Рыцарей находятся в одной клетке, игрок может переместить Короля и одного из Рыцарей вместе по правилам перемещения Рыцаря и считать это одним ходом.
Напишите программу для вычисления минимального количества ходов, необходимых для перемещения всех фигур в одну клетку доски.
Входной файл содержит одну строку символов, описывающую начальное расположение фигур на доске. Строка содержит последовательность клеток доски, первая из которых – клетка Короля, остальные – клетки Рыцарей (количество Рыцарей не более 63). Каждая клетка описывается парой буква-цифра. Буква обозначает горизонтальную, а цифра – вертикальную координату клетки доски. Все фигуры в начале игры расположены в разных клетках.
Выходной файл должен содержать единственную строку с положительным целым числом, обозначающим минимальное число ходов игрока, необходимых для перемещения всех фигур в одну клетку доски.