Автор: | Жюри зимних сборов 2009 | Ограничение времени: | 15 сек | |
Входной файл: | chess.in | Ограничение памяти: | 128 Мб | |
Выходной файл: | chess.out | |||
Максимальный балл: | 50 |
В неофициальном матче по шахматам встречаются шестой чемпион мира Михаил Ботвинник и одиннадцатый чемпион Роберт Фишер. Идёт сотая игра матча. Сделано уже больше сотни ходов. После десятого перерыва в партии Михаил и Роберт решили закончить партию максимально быстро, благо их не очень волновал её результат. К счастью, на доске осталось всего 4 фигуры. У каждого из гроссмейстеров осталось по одной тяжёлой фигуре (ладья или ферзь) и, естественно, королю. Игра считается законченной, когда один из королей заматован, или у каждой из сторон остался только король. В первом случае игрок, которого заматовали, проигрывает, а во втором объявляется ничья. Все другие правила окончания игры (в том числе правило троекратного повторения позиции и правило пятидесяти ходов) в этой партии отменены.
Ваша задача — найти самый быстрый способ закончить игру.
На первой строке находится описание позиции белых фигур, на второй — чёрных. Каждая фигура определяется тремя символами. Первый — это тип фигуры: K — это король, Q — ферзь, а R — ладья. Второй и третий символ содержат описание клетки, на которой стоит данная фигура, буква соответствует номеру вертикали, а цифра — горизонтали. Например, Ka1 обозначает, что король стоит в левой нижней клетке доски. Описания фигур внутри строки разделяются пробелом. Гарантируется, что позиция корректна. Право хода в данной позиции принадлежит чёрным. Первой фигурой в каждой строке является король.
Выведите кратчайшую последовательность ходов, приводящую к концу игры. каждый ход записывается шестью символами: первый это название фигуры, следующие два это клетка, на которой фигура стояла до хода, четвёртый это дефис ('-'), а пятый и шестой — клетка, в которую фигура походила. Если оптимальных решений несколько разрешается вывести любое.
№ | Входной файл (chess.in ) |
Выходной файл (chess.out ) |
---|---|---|
1 |
|
|
2 |
|
|