Šeštadieninė informatikos olimpiadininkų mokykla

Garsusis lobių ieškotojas Adas neretai klaidžioja piramidėse, kurių lobių žmonija dar nerado. Gal jis bus pirmasis? Painūs koridoriai ir kiek­viename žingsnyje paspęsti spąstai toli gražu nė­ra sunkiausia jo tyrinėjimų dalis. Kur kas blogiau, kai Adą pradeda vytis mumija... arba dvi.

Žvelgiant iš viršaus piramidę galima įsivaizduoti kaip N eilučių ir M stulpelių lentelę – ši analogija padės lengviau paaiškinti Ado patiriamą siaubą. Du langeliai yra gretimi, jei jie turi bendrą briauną. Tarp kai kurių gretimų langelių yra sienos. Vienas iš langelių, esančių piramidės krašte, turi duris, vedančias laukan, kur mumijos, be abejo, neina¹. Viename iš langelių stovi Adas...

Kaip žinia, susidūrus su mumijomis, lobių ieškotojai ir mumijos juda paeiliui: Adui paėjus vieną kartą, kiekviena mumija paeina du kartus. Adas savo ėjimu gali pereiti į gretimą langelį, neatitvertą siena, arba stovėti vietoje. Kol savo ėjimus atlieka mumijos, Adas stovi sustingęs iš siaubo. Jei piramidėje yra dvi mumijos, jos abi juda tuo pačiu metu. O kaip jos juda?

Geras klausimas! Per ilgus lobių ieškojimo metus Adas perprato išdžiūvusią mumijų mąstyseną. Jei mumija yra ne tame pačiame stulpelyje kaip Adas, ji eis į kairę ar į dešinę, jo link, o jei taip paeiti trukdo siena arba mumija jau yra tame pačiame stulpelyje kaip Adas, mumija bandys artėti judėdama į viršų arba į apačią. Jeigu ir šia kryptimi judėti mumijai trukdo siena, ji tiesiog lauks. Atkreipiame dėmesį, kad, paėjusi pirmą ėjimą, mumija iš naujo mąsto, kur toliau eiti, o ne tiesiog kartoja pirmą ėjimą.

Jei mumija atsidurtų tame pačiame langelyje, kuriame yra Adas... na, geriau taip neatsitiktų. Mumijų tarpusavio santykiai taip pat nėra labai šilti, tad, jei abi mumijos atsiduria viename langelyje, vienai iš jų tai reiškia ilgo gyvenimo pabaigą.

Pavargęs nuo nuolatinio mumijų persekiojimo, Adas pažadėjo atiduoti trečdalį rastų lobių tam, kuris parašys programą, randančią greičiausią būdą sveikam pabėgti iš piramidės.

Pradiniai duomenys

Pirmoje eilutėje įrašyti kambario dydį nusakantys skaičiai N ir M bei mumijų skaičius K (, ). Kiekvienoje tolesnių N eilučių yra M tarpais atskirtų sveikų skaičių , kurie nurodo kuriose atitinkamo langelio pusėse yra sienos.

yra šių skaičių suma:

1, jei langelis turi sieną viršuje; 2, jei langelis turi sieną dešinėje; 4, jei langelis turi sieną apačioje; 8, jei langelis turi sieną kairėje. Taigi, pavyzdžiui, = 9 reiškia, kad langelis turi sienas kairėje ir viršuje (8 + 1 = 9). Visi kraštiniai piramidės langeliai turi išorines sienas, išskyrus vieną langelį, kuriame bus išėjimas.

Tolesnėje eilutėje yra du sveiki skaičiai, langelio, kuriame Adas stovi, eilutės ir stulpelio numeriai. Likusiose K eilučių analogiškai parašyta, kur stovi mumijos. Eilutės ir stulpeliai numeruojami nuo 1 iki N ir M, atitinkamai.

Rezultatai

Pirmoje eilutėje turi būti mažiausias pakankamas ėjimų skaičius Z. Antroje eilutėje turi būti Z simbolių, nurodančių pačius ėjimus:

< (ASCII kodas 60) – ėjimas kairėn > (ASCII kodas 62) – ėjimas dešinėn ^ (ASCII kodas 94) – ėjimas viršun v (ASCII kodas 118) – ėjimas apačion x (ASCII kodas 120) – laukimas vietoje

Pavyzdys

Pradiniai duomenys	Rezultatai	Paaiškinimas
4 3 1 9 4 3 8 3 10 14 8 2 13 4 6 4 1 2 2	7 x>^>^^<	Jei Adas pirmu ėjimu paeitų į dešinę, mumija paeitų du kartus žemyn ir ... Kadangi Adas palaukia, mumija paeina kairėn ir žemyn. Ten ji prabūna iki penkto Ado ėjimo, po kurio mumija grįžta į savo pradinį langelį.

1-Galbūt jus suklaidino Holivudo filmai.