Проблема мандрівної королеви#2530
Чорні були переможені, і біла армія здобула перемогу, але, на жаль, білий король загинув у битві. Тому біла королева шукає нового супутника життя. Вона не впевнена, якого з лицарів (коней) вибрати, тому вирішила відвідати всіх. Після цього вона планує завітати до слона, щоб організувати весілля.
Дано шахівницю з поточним розташуванням фігур, знайдіть мінімальну кількість ходів, необхідних для того, щоб королева відвідала кожного коня і, нарешті, відвідала слона.
Королева вважається такою, що відвідала фігуру, якщо знаходиться на одній з (максимум) восьми сусідніх клітин; їй не обов'язково рухатися між двома відвідуваннями. За один хід королева може переміститися на будь-яку кількість клітин в одному з восьми напрямків (по горизонталі, вертикалі або діагоналі). Жоден хід не може проходити через зайняту фігуру або закінчуватися на ній.
Перший рядок містить кількість сценаріїв. Кожен сценарій складається з опису шахівниці. Рядки 8, \ldots, 1 подаються саме в такому порядку, по одному рядку на кожен рядок дошки. Кожен рядок містить символів, що представляють клітини стовпців a, \ldots, h цього рядка. Після кожного опису подається порожній рядок.
Один символ позначає початкову позицію королеви, а один — клітину, на якій стоїть слон. Може бути будь-яка кількість пішаків, позначених як , які просто блокують рух, а також від до коней, позначених як . Всі інші клітини позначені як і є порожніми.
Для кожного сценарію вивід починається з рядка "\textbf{Scenario #i:}", де — номер сценарію починаючи з .
Далі необхідно вивести лексикографічно перший шлях, який містить мінімальну кількість ходів, закінчується на клітині, суміжній зі слоном, і який відвідує кожного коня принаймні один раз. Шлях слід вказати в одному рядку, конкатенуючи назви клітин, на яких стояла королева, у відповідному порядку. Назва кожної клітини складається з маленької літери та десяткової цифри. Якщо такого шляху не існує, виведіть у одному рядку "". Вивід для кожного сценарію завершується порожнім рядком.
Приклад 1