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