Задача о путешествующей королеве
Черные потерпели поражение, и белая армия одержала победу. Однако, к сожалению, белый король пал в бою, и теперь белая королева ищет нового спутника. Она не уверена, за кого из рыцарей выйти замуж, и решила посетить их всех. После этого она планирует встретиться с епископом, чтобы организовать свадьбу.
На шахматной доске представлена текущая ситуация. Ваша задача — найти минимальное количество ходов, чтобы королева посетила каждого рыцаря и, в конце концов, встретилась с епископом.
Королева может перемещаться, становясь на одну из (максимум) восьми соседних клеток, и ей не обязательно перемещаться между двумя посещениями. За каждый ход королева может пройти произвольное количество клеток в одном из восьми направлений (горизонтально, вертикально или по диагонали). Ни один ход не может проходить через или останавливаться на занятой клетке.
Входные данные
Первая строка содержит количество сценариев. Каждый сценарий состоит из описания шахматной доски. Строки 8,...,1 даны в этом порядке, по одной строке на рядок. Каждая строка содержит 8 символов, представляющих клетки в столбцах a,...,h этой строки. Каждое описание сопровождается пустой строкой.
Один символ Q обозначает начальную позицию королевы, и один B обозначает клетку, на которой стоит епископ. Существует произвольное количество пешек, обозначенных как P, которые просто блокируют движение, а также 2-14 рыцарей, обозначенных как N. Все остальные клетки обозначены как '.' и являются пустыми.
Выходные данные
Вывод для каждого сценария начинается с строки, содержащей "Сценарий #i:", где i — это номер сценария, начиная с 1.
Затем выведите лексикографически первый путь, который содержит минимальное количество ходов, заканчивается рядом с епископом и посещает каждого рыцаря хотя бы один раз. Путь должен быть дан в одной строке, объединяя в порядке названия клеток, на которых стоит королева. Каждое название клетки состоит из маленькой буквы, за которой следует десятичная цифра. Если такого пути не существует, выведите "невозможно" в одной строке. Завершите вывод для сценария пустой строкой.