Šeštadieninė informatikos olimpiadininkų mokykla

Trenksmas, blyksnis, ir... Haris atsimerkia tamsiame kambaryje, nors į akį durk. Veriantis skausmas pakaušyje byloja, jog krisdamas jis susitrenkė galvą. Ištiesęs rankas suprato esąs mažulyčiame uždarame kvadratiniame kambarėlyje be jokių durų. Laimei, lazdelė liko sveika.

Pasitelkęs skenavimo kerus Haris išsiaiškino nė kiek nedžiuginantį faktą: visomis kryptimis jį supa daug tokių pačių uždarų kambarėlių. Tačiau kai kas jam suteikė vilties – gretimame kambaryje buvo Ronis, vis dar gyvas.

– Roni, ar girdi? – šūktelėjo per sieną Haris.
– Sunkiai, bet taip.
– Ar viskas gerai?
– Beveik.
– Ar turi kokių nors minčių, kaip iš čia ištrūkti?
– Viršuje jokio išėjimo nėra, tačiau galėtume pabandyti prasmukti pro sienas. Kai kurios jų yra plonesnės, negu kitos. Jeigu sujungtume savo lazdelių galias, galėtume vieną mūsų perkelti per ploną sieną. Deja, kambariai tokie maži, kad mes niekaip abu viename netilptume. Tačiau mes visada turime būti kambariuose, turinčiuose bent vieną bendrą kampą, kad galėtume palaikyti ryšį.
– Gerai, kito kelio neturime – bandom.

Haris nupiešė kambarių planą, kuriame pažymėjo plonas ir storas sienas. Paaiškėjo, jog visi kambariai kartu suformavo stačiakampį, už kurio nebėra jokių sienų, taigi ten galima judėti laisvai. Dabar Haris ir Ronis turi susidaryti planą, kaip judėti tarp kambarių, kad abu ištrūktų iš spąstų.

Pradiniai duomenys

Pirmoje eilutėje – stačiakampio matmenys ir . Tolesnėse eilutėse vaizduojamas Hario nupieštas žemėlapis. Kiekvienoje iš eilučių yra po simbolį. Haris ir Ronis pažymėti raidėmis „H“ ir „R“; jų kambariai turi bent vieną bendrą kampą. Simboliai „|“ ir „-“ žymi storas sienas, simbolis „.“ – ploną sieną, „+“ – kampą, o „ “ – tuščią kambarį.

Rezultatai

Jeigu Haris arba Ronis negali ištrūkti iš spąstų, išveskite žodį „Mirtis“. Priešingu atveju, išveskite minimalų kiekį persikėlimų per ploną sieną, kuriuos jie turi atlikti, kad abu išsilaisvintų.

Pavyzdys

3 4
+.+-+-+-+
| . .H. |
+-+-+-+.+
| .R. . |
+.+.+.+-+
| . | | |
+.+.+-+-+

13

1 2
+-+-+
.H|R.
+-+-+

Mirtis