Müəmmalı Zindanlar#3623
Aqua Canora Mystica Krallığı, gizli xəzinələrlə və çətin tapmacalarla dolu sirli zindanları ilə məşhurdur. Bir gün, dərin bir zindanı araşdırarkən, nəhayət əfsanəvi artefaktın olduğu deyilən qədim otağa gedən yolu tapırsan.
Lakin, artefakta yaxınlaşan kimi bir sehrli tələ işə düşür! Birdən-birə qəribə xalçalar və nəhəng qayalar zindanın hər yerində peyda olur, çıxış yolunu bağlayır. Qayalar və xalçalar zindanın qurucuları tərəfindən qoyulmuş qədim qoruma sehrləri sayəsində sehrli şəkildə yaradılıb. Hər bir qaya tam bir xanayı tutur və həmin xanadan keçmək mümkün deyil. Hər bir xalça da dəqiq olaraq bir xanayı örtür. Bütün qayaların üzərində böyük bir hərf, xalçaların üzərində isə kiçik bir hərf yazılıb. Bəzi qaya və xalçalarda eyni yazı ola bilər.
Qaçmağa çalışarkən aşağıdakı qəribə davranışı müşahidə edirsən: Əgər xalça üzərinə addım atsan, həmin kiçik hərfə uyğun olan bütün qayalar (məsələn, xalçası üçün qayaları) yox olur. Bundan sonra həmin qayaların olduğu xanalara daxil ola bilərsən. Lakin əgər həmin xalçanın üstünə yenidən, və ya eyni yazılı başqa bir xalçanın üstünə çıxarsansa, qayalar yenidən peyda olur və səni dayandırır. Qayaların yenidən yox olması üçün müvafiq xalçaya bir daha çıxmalısan.
Zindandan qaça bilərsənmi? Əgər mümkünsə, çıxışa ən qısa müddətdə necə çata bilərsən? Sənin vəzifən proqram tərtib etməkdir ki, zindandan çıxmağın mümkün olub-olmadığını yoxlasın və ən az vaxtı hesablansın.
Daxil olan məlumat bir neçə məlumat dəstindən ibarətdir. Hər məlumat dəstinin ilk sətrində iki tam ədəd — və (3 \leq W, H \leq 30) verilir. Növbəti sətrin hər birində zindan xəritəsini təsvir edən, simvolu verilir və bu da W \times H ölçülü xanalar şəbəkəsini göstərir. Hər bir simvol aşağıdakılardan biri ola bilər:
— sizin hazırkı mövqeyinizi göstərir,
— zindanın çıxışını göstərir,
kiçik hərf — həmin hərflə yazılmış bir xalça ilə örtülmüş xana,
böyük hərf — həmin hərflə işarələnmiş qaya ilə tutulan xana,
\textbf{#} — divarı göstərir,
— boş xana.
Hər bir zindan divar xanalardan (\textbf{#}) ibarət çərçivə ilə əhatə olunub və xəritədə məhz bir və bir xanası olur. Qayalarda ən çox səkkiz fərqli böyük hərf, xalçalarda isə ən çox səkkiz müxtəlif kiçik hərf ola bilər. Hər dəfə bir saniyəyə, bitişik (yuxarı, aşağı, sağa, sola) xanaya keçmək olar. Divarlardan və qaya xanalardan keçmək olmaz. Giriş xəttində iki sıfır verilirsə, bu girişin sonudur və işlənməməlidir.
Hər məlumat dəsti üçün xanasından xanasına ən az neçə saniyəyə çatmaq olar? Əgər çıxmaq mümkün deyilsə, bir sətrdə çap edin.
Nümunə 1