Mina Xəritəsi
Son oğurluq hadisəsindən sonra ACM ICPC Dünya finalı üçün problem dəstinin (məşhur britaniyalı super casus James B. tərəfindən - bu barədə bir neçə həftə əvvəl məlumat vermişdik) ACM bütün gələcək problem dəstlərini yüksək təhlükəsizlikli bir binada saxlamağa qərar verdi. Təhlükəsizlik şurası yeni seyfi nəhəng bir labirint şəklində tikməyi təklif etdi. Bu labirint kvadrat otaqlardan ibarətdir, kvadrat matrisi şəklində düzülmüşdür və bütün otaqlar bir-birinə qapılar vasitəsilə bağlıdır. Problem dəstlərinin saxlandığı mərkəzə çatmağın yeganə yolu bu otaqlardan keçməkdir.
Aydındır ki, bütün otaqların bir-birinə bağlı olduğu bir labirintdən keçmək o qədər də çətin deyil. Beləliklə, potensial müdaxiləçilər üçün işləri daha təhlükəli etmək üçün bəzi otaqlar mina ilə tələyə salınmışdır. Kimsə problem dəstlərinin saxlandığı seyfin mərkəzi otağına daxil olarsa, bu minalar aktivləşdirilir. Bundan sonra, mina olan bir otağa aparan qapını açmaq siqnalizasiya sistemini işə salacaq və bütün təhlükəsizlik qapıları dərhal bağlanacaq, müdaxiləçini tələyə salacaq. Bu yolla, ACM casusu göndərən ölkəni müəyyən edə bilər və həmin ölkənin bütün komandalarını diskvalifikasiya edə bilər.
Lakin son zamanlarda təhlükəsizlik şurası aktivləşdirildikdən sonra minaları aşkar edə bilən yeni bir skan cihazından xəbərdar oldu. Bu detektor seyfin istənilən otağından istifadə edilə bilər və istifadəçiyə bitişik səkkiz otaqdan hər hansı birində mina olub-olmadığını bildirə bilər. Təəssüf ki, şura artıq bu minalardan bir partiya sifariş etmişdi və indi bunun səhv ola biləcəyini etiraf etmək istəmir. Bunun əvəzinə, minaları elə bir şəkildə yaymaq istəyirlər ki, cihazdan istifadə edərək mərkəzdən çıxmaq çətin olsun. Siz seyfi inşa edən komandaya onların dizaynlarını qiymətləndirməkdə kömək etmək üçün təyin olunmusunuz.
Seyf dörd tərəfli bir forma malikdir, tərəfləri tək uzunluqludur. Seyfdəki hər bir otaq binanın sabit bir küncünə nisbətən üfüqi və şaquli ofseti göstərən koordinat cütü ilə təsvir edilə bilər. Hər otaqda qonşu otaqlara aparan qapılar var; daha əhəmiyyətlisi, mina detektoru səkkiz bitişik otağın hamısında minaları aşkar edə bilər. Cihaz sizə yaxınlıqda mina olub-olmadığını bildirə bilər, lakin onların sayını deyə bilməz.
Sizin işiniz hər bir seyf dizayn layihəsindən xüsusi bir xəritə yaratmaqdır. Xəritədə, mərkəzi otaqdan (mina olmadığına zəmanət verilən) başlayaraq yeni detektorun köməyi ilə və aşağıdakı sadə strategiya ilə təhlükəsiz şəkildə çata biləcək bütün otaqları işarələyin: Detektorun heç bir bitişik minaların olmadığını bildirdiyi bir otaqda olduğunuzda, ətrafdakı bütün otaqları axtarın. Əks halda, mina işə salma riski etməyin və bu otaqdan daha uzağa getməyin (bəlkə də daha sonra başqa bir "təhlükəsiz" marşrutla ətrafdakı otaqlardan birinə çata bilərsiniz).
Beləliklə, müdaxiləçi minalara yaxın olmayan bir otaqda olduqda, o, ətrafdakı bütün otaqlara gedə biləcək - belə bir otağı "." ilə işarələyin. Müdaxiləçi bir və ya daha çox minalara yaxın bir otağa daxil olarsa, geri çəkiləcək - bu otaqları "#" ilə işarələyin. İşinizi təsdiqləmək üçün təhlükəsizlik şurası sizdən hər bir minanın yerini "*" ilə işarələməyinizi də istəyir. Nəhayət, qalan bütün otaqlar "?" ilə işarələnməlidir.
Giriş verilənləri
Birinci sətir ssenarilərin sayını ehtiva edir. Hər bir ssenari, seyfin xarici divarlarından birinin uzunluğunu göstərən tək rəqəmli n (1 < n < 300) rəqəmi ilə başlayan bir sətirlə başlayır. Bu, seyfdəki otaqların sayına məhdud olan müsbət və yalnız minaların sayını göstərən m rəqəmi ilə davam edir. Sonra m sətir gəlir, hər biri mina olan sətir və sütunu verən iki tam ədəd r və c (1 ≤ r, c ≤ n) ehtiva edir.
Çı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 yuxarıda təsvir edilən seyfin xəritəsinin ASCII təsvirini çap edin. Ssenarinin çıxışını boş bir sətirlə tamamlayın.