Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
156. Шахматный диверсант
Поиск в ширину (BFS)Олимпиадные задачи на русском языке
| 17/03/2007 | Южно-Уральский открытый командный чемпионат по программированию ( 5) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Диверсант должен уничтожить все фигуры на шахматной доске. Для этого он уничтожает любую из стоящих на доске фигур и превращается в неё. После превращения он должен делать ходы по шахматным правилам, пока не уничтожит следующую фигуру, при этом он должен снова превратиться во взятую фигуру. Напишите программу, вычисляющую минимальное число ходов для уничтожения всех фигур на доске.
В первой строке ввода содержится одно целое число `N\ (1≤N≤10)` – количество фигур на доске. В следующей строке содержится `N` групп из 3 символов. Первый символ указывает тип фигуры: 'K' – король, 'Q' – ферзь, 'B' – слон, 'H' – конь, 'R' – ладья. Второй и третий символы указывают местонахождение фигуры на доске: вертикаль задается буквой от 'a' до 'h', а горизонталь – цифрой от '1' до '8'. Все фигуры находятся в разных клетках доски.
Вывести одно число – минимальное число ходов для уничтожения всех фигур на доске. Если уничтожение всех фигур невозможно, вывести –1.
Пример ввода
3 Ha1 Kc5 Qd6
Вывод для примера
3
