Səyahət edən Kraliça Problemi
Qara məğlub olub və ağ ordu qalib gəlib, lakin təəssüf ki, ağ şah döyüşdə öldürülüb. Buna görə də ağ şahmat kraliçası yeni həyat yoldaşı axtarır. O, hansı cəngavərlə evlənəcəyinə əmin deyil və hamısını ziyarət etməyə qərar verir. Daha sonra evliliyi təşkil etmək üçün yepiskopa müraciət etməyi planlaşdırır.
Cari vəziyyəti olan bir şahmat taxtası verildikdə, kraliçanın hər bir cəngavəri ziyarət etməsi və nəhayət, yepiskopu ziyarət etməsi üçün ən qısa hərəkət sayını tapın.
Kraliça ziyarətləri ən çox səkkiz qonşu kvadratın birində dayanaraq edir və iki ziyarət arasında mütləq hərəkət etməli deyil. Hər bir hərəkət üçün kraliça səkkiz istiqamətdən birində (üfüqi, şaquli və ya diaqonal) istənilən sayda kvadrat keçə bilər. Heç bir hərəkət dolu olmayan bir kvadratın üzərindən keçə və ya orada dayana bilməz.
Giriş verilənləri
Birinci sətir ssenarilərin sayını ehtiva edir. Hər bir ssenari bir şahmat taxtası təsvirindən ibarətdir. Sətirlər 8,...,1 bu qaydada verilir, hər sətir üçün bir sətir. Hər sətir bu sətirin sütunlarındakı a,...,h kvadratlarını təmsil etmək üçün 8 simvol ehtiva edir. Hər bir təsvir boş bir sətirlə tamamlanır.
Kraliçanın başlanğıc mövqeyini göstərən bir Q simvolu və yepiskopun dayandığı kvadratı göstərən bir B simvolu var. Hərəkəti sadəcə bloklayan istənilən sayda piyadalar P ilə göstərilir, həmçinin 2-14 cəngavərlər N ilə göstərilir. Bütün digər kvadratlar '.' kimi verilir və boşdur.
Çıxış verilənləri
Hər bir ssenari üçün çıxış "Ssenari #i:" sətiri ilə başlayır, burada i 1-dən başlayan ssenarinin nömrəsidir.
Sonra minimal hərəkət sayını ehtiva edən, yepiskopun yanında bitən və hər bir cəngavəri ən azı bir dəfə ziyarət edən leksikoqrafik ilk yolu çap edin. Yol kraliçanın dayandığı kvadratların adlarını ardıcıl olaraq bir sətirdə birləşdirərək verilməlidir. Hər bir kvadrat adı kiçik hərflə başlayan və ondalık rəqəmlə davam edən bir simvoldan ibarətdir. Əgər belə bir yol mövcud deyilsə, bir sətirdə "impossible" çıxış edin. Ssenari üçün çıxışı boş bir sətirlə tamamlayın.