Задача №114481. Конный спорт
Как известно, шахматы — это вид спорта. Однако далеко не все с этим согласны. Например, первокурсник Дима, занимающийся конным спортом, считает, что такую скучную вещь как шахматы спортом назвать никак нельзя. Когда его друг-шахматист Саша об этом узнал, он сразу решил, что надо показать Диме, насколько сложными и интересными на самом деле бывают шахматы, и дал Диме задачку, решать которую тому бы точно понравилась.
На шахматной доске \(8 \times 8\) Саша расставил \(k\) коней. Эти кони давно вышли на прогулку и хотят поскорее вернуться в стойла. К сожалению, кони не помнят пути обратно.
Будем говорить, что кони находятся в стойлах, если выполнены следующие условия: несколько (а именно, \(k \div 8\)) нижних строк доски полностью заполнены конями, а следующая строка может содержать оставшихся коней в нескольких самых левых клетках (если \(k \mod 8 \ne 0\), то \(k \mod 8\) коней занимают самые левые клетки следующей строки).
На данном рисунке показаны возможные ходы шахматного коня.
Разумеется, поскольку это шахматная задача, то все кони тоже ходят как шахматные — ровно на две клетки по одной координате и ровно на одну по другой.
В этих клетках, по одному в каждой, в конце должны оказаться \(k=11\) коней.
Кони делают ходы по одному. В каждый момент времени в одной клетке может находиться не более одного коня.
За два дня решения этой задачи Дима понял, что шахматы не такие уж и скучные. Но всё же она ему немного надоела, так что он просит вас о помощи — найдите такой порядок ходов коней, чтобы в каждый момент времени в каждой клетке было не более одного коня, и в конце кони находились в стойлах. Минимизировать количество ходов не требуется, но необходимо сделать не слишком много перемещений коней — не больше 1500.
В первой строке входных данных задано число \(k\) — количество коней на доске (\(1 \leq k \leq 64\)). Далее следуют \(k\) строк с описаниями коней — на каждой строке записана позиция коня на поле в формате xy , где x — буква столбца, а y — номер строки.
Столбцы обозначены буквами от « a » до « h » слева направо, строки пронумерованы цифрами от 1 до 8 снизу вверх.
В первой строке выведите суммарное количество ходов, за которое кони добираются до стойл. Затем выведите по одному в строке ходы коней в порядке их совершения, каждый в формате xy-zt , где x и z — столбцы, а y и t — строки.
Обратите внимание, не требуется минимизировать число ходов, но их число должно быть не более \(1500\).
2 a5 f1
4 a5-b3 b3-a1 f1-d2 d2-b1
3 a1 b3 c2
3 b3-c1 c2-a3 a3-b1