İkimərtəbəli zindan#5836
Yay təlim düşərgəsinin son günü idi və siz birdən-birə Tokionun Komaba kampusuna gedərkən labirintdə azdınız. Yarış yeni başlamışdı və komanda yoldaşlarınız səbirsizliklə sizi gözləyirlər. Labirintdən mümkün qədər tez çıxmalısınız.
Labirint bir şəbəkə xəritəsi şəklində təqdim olunur. Əvvəlcə divarlar və pilləkənlərdən başqa hər bir hücrə ya birinci, ya da ikinci mərtəbədə yerləşir. Bəzi hücrələrdə sizi yuxarı və ya aşağı hərəkət etdirə bilən açarlar var (birinci mərtəbədəki hücrələr ikinci mərtəbəyə, ikinci mərtəbədəki hücrələr isə birinci mərtəbəyə hərəkət edir).
Hər addımda aşağıdakı hərəkətlərdən birini edə bilərsiniz:
Olduğunuz mərtəbədə qonşu hücrəyə (pilləkən daxil olmaqla) keçin.
Başqa mərtəbəyə keçin (əgər pilləkən olan hücrədəsinizsə).
Açarı istifadə edin (əgər açar olan hücrədəsinizsə).
Xoşbəxtlikdən, siz az əvvəl labirintin xəritəsini tapdınız. Labirintdən qaçmaq və komanda yoldaşlarınızın sizi gözlədiyi yerə çatmaq üçün lazım olan ən az hərəkət sayını hesablayın!
Giriş məlumatlarının formatı aşağıdakı kimidir.
W H
M_11M_12M_13…M_1W
M_21M_22M_23…M_2W
........
M_H1M_H2M_H3…M_HW
S
MS_111MS_112MS_113…MS_11W
MS_121MS_122MS_123…MS_12W
........
MS_1H1MS_1H2MS_1H3…MS_1HW
MS_211MS_212MS_213…MS_21W
MS_221MS_222MS_223…MS_22W
........
MS_2H1MS_2H2MS_2H3…MS_2HW
MS_S11MS_S12MS_S13…MS_S1W
MS_S21MS_S22MS_S23…MS_S2W
........
MS_SH1MS_SH2MS_SH3…MS_SHW
Birinci sətir iki tam ədəd W (3 ≤ W ≤ 50) və H (3 ≤ H ≤ 50) - labirintin eni və hündürlüyünü ehtiva edir.
Növbəti H sətir labirintin başlanğıc vəziyyətini təsvir edir. Hər bir M_ij aşağıdakı simvollardan biridir:
'#' divarı təyin edir,
'|' pilləkəni təyin edir,
'_' birinci mərtəbədə yerləşən hücrəni təyin edir,
'^' ikinci mərtəbədə yerləşən hücrəni təyin edir,
kiçik hərflər 'a' ilə 'j' arasında olan hərf, hücrədə açarın olduğunu göstərir, hücrə əvvəlcə birinci mərtəbədədir,
böyük hərflər 'A' ilə 'J' arasında olan hərf, hücrədə açarın olduğunu göstərir, hücrə əvvəlcə ikinci mərtəbədədir,
'%' başlanğıcda olduğunuz hücrəni təyin edir (və o, birinci mərtəbədə yerləşir),
'' labirintdən çıxışı təyin edir (o, əvvəlcə birinci mərtəbədədir).
Növbəti sətir S (0 ≤ S ≤ 10) dəyərini ehtiva edir və növbəti S*H sətir açarlarla bağlı məlumatı təsvir edir. Hər bir MS_kij aşağıdakılardan biridir:
'#' əgər Mij '#' bərabərdirsə,
'|' əgər Mij '|' bərabərdirsə,
'*' əgər hücrə k-cı hərflə təmsil olunan açarla hərəkət edirsə,
'.' əks halda.
Açar olan hücrə, açarın vəziyyətini dəyişməklə hərəkət etdirilə bilər. Bu halda siz hücrə ilə birlikdə hərəkət edirsiniz.
Xəritədə '%' (başlanğıc) və '' (məqsəd) simvolları dəqiq bir dəfə mövcuddur, xəritə divarlarla əhatə olunub, xəritədə yalnız 'A' (və ya 'a') hərfindən S-cı hərfə qədər olan hərflər mövcuddur.
Məqsədə çatmaq üçün lazım olan ən az hərəkət sayını çıxarın. Əgər həll mövcud deyilsə, "-1" çıxarın.
Nümunə 1