Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_1998_3e2_lobis_jau.in

Rezultatų failas: lmio_1998_3e2_lobis_jau.out

Jei norite pateikti savo sprendimą - prisijunkite.

Lobio ieškojimas

Tarkime, turime 4\\times4 laukelių labirintą. Keliautojo tikslas – kuo greičiau rasti paslėptą lobį ir išeiti iš labirinto. Į labirintą galima patekti tik pro vieną kurioje nors išorinėje sienoje esantį plyšį – tai drauge įėjimas ir išėjimas. Būdamas labirinte (t.y. kuriame nors laukelyje) keliautojas gali eiti bet kuria iš keturių krypčių: į viršų, į apačią, į kairę, į dešinę, žinoma, jei tik netrukdo sienos. Įstrižai eiti negalima.

Labirinto pavyzdys pateiktas paveiksle.

image

Kiekvienas labirinto laukelis yra tam tikros rūšies. Iš viso esama šešių rūšių laukelių:

  • Sausuma S. Tokių laukelių labirinte yra penki.
  • Trys duobės D_1, D_2, D_3. Jei keliautojas ateina į laukelį D_1, tai jis permetamas į laukelį D_2 ir iš ten atlieka tolesnį ėjimą. Analogiškai patekęs į laukelį D_2, keliautojas permetamas į D_3, o atsidūręs laukelyje D_3, patenka į laukelį D_1.
  • Pelkė P. Ji viena. Pelke prasideda upė.
  • Žiotys Ž. Jos vienos – jomis baigiasi upė.
  • Upė. Ją sudaro penki laukeliai U_1, U_2, U_3, U_4, U_5. Upėje atsidūrusį keliautoją neša srovė. Iš laukelio U_1 jis patenka į U_4, iš U_2 – į U_5. Jei keliautojas patenka į kitus tris upės laukelius, jis nunešamas į žiotis Ž. Toliau keliautojas turės tęsti kelionę iš laukelio, į kurį jį atnešė srovė. Visi upės laukeliai susisiekiantys, t. y. U_1 turi bendrą kraštinę su U_2, U_2 su U_3, ir t. t. Pelkė P susisiekia su U_1, o žiotys Ž – su U_5.
  • Lobis L. Laikoma, jog lobis surastas, kai keliautojas atsistoja laukelyje L.

Labirinte yra dvi tiesios sienos: viena trijų laukelių ilgio, kita – dviejų (jos eina laukelių pakraščiu). Siena niekuomet nekerta upės, neatskiria pelkės arba žiočių nuo upės. Be to, abi sienos negali viena su kita liestis. Vienas sienos galas visada liečiasi su labirinto išorine siena.

Keliautojas turi du užtaisus sienoms sprogdinti. Sienos sprogdinimas lygus vienam ėjimui. Išsprogdinęs skylę sienoje, keliautojas gali pro ją pralįsti. Sprogdinant sieną, sugriaunamas tik vienas sienos laukelis, o ne visa siena. Susprogdintos sienos neatsistato. Draudžiama sprogdinti išorines labirinto sienas, t. y pasidaryti išėjimą. Keliautojas gali ir nepanaudoti sprogmenų arba panaudoti tik vieną.

Sprogdinti galima iš bet kurių laukelių. Jei sprogdinama iš laukelių, į kuriuos keliautojas buvo permestas ar jį į ten atnešė srovė, po sprogdinimo keliautojas pasilieka tame pačiame langelyje. Pirmu ėjimu po sprogdinimo keliautojas gali lįsti pro skylę arba eiti į kitą gretimą laukelį (t. y. jis nebus iš karto permestas į kitą duobę bei jo nenuneš srovė). Beje, tai yra vienintelis atvejis, kai keliautojas pasilieka tame pačiame langelyje.

Įėjimas į labirintą bei išėjimas iš labirinto laikomas ėjimu. Permetimas iš vienos duobės į kitą arba nunešimas pagavus srovei nėra ėjimas.

Užduotis

Parašykit eprogramą, kuri pagal duotą labirintą nustatytų, kiek mažiausiai ėjimų reikia, kad keliautojas rastų lobį ir išeitų iš labirinto.

Pradiniai duomenys

Pirmoje eilutėje pateikti du skaičiai – laukelio, į kurį patenkama įėjus į labirintą, koordinatės (x,y). Tolesnėse 16-oje eilučių įrašyta po du skaičius – visų labirinto laukelių koordinatės (x,y). Koordinatės išdėstytos tokia tvarka: P, U_1, U_2, U_3, U_4, U_5, Ž, penkių S laukelių koordinatės, D_1, D_2 , D_3, L.

Paskutinėse dviejose eilutėse yra po tris skaičius. Pirmoje iš jų aprašyta dviejų laukelių ilgio siena, antroje – trijų. Pirmasis skaičius eilutėje parodo, prie kurios labirinto išorinės sienos liečiasi vidinė siena: skaičius 1 nurodo lietimąsi su viršutine siena, 2 – su dešiniąja, 3 – su apatine, 4 – su kairiąja. Kiti du skaičiai nusako tarp kurių eilučių ar stulpelių yra siena (žr. žemiau pateiktą pavyzdį).

Pradiniai duomenys tokie, kad sprendinys visuomet egzistuoja.

Rezultatai

Rezultatas – minimalus ėjimų skaičius.

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas 
3 1 
1 3 
1 2 
1 1 
2 1 
3 1 
4 1 
4 2 
3 2 
2 3 
1 4 
2 4 
4 4 
2 2 
4 3 
3 4 
3 3 
2 2 3 
3 1 2
 
8
 
Atsakyme pateiktas vienas iš galimų ėjimų variantų: 
1. pro įėjimą patenkama į U_4 ir upė nuneša į žiotis Ž, 
2. sprogdinama siena tarp Ž ir D_2, 
3. iš Ž pro skylę sienoje einama į D_2, keliautojas permetamas į D_3, 
4. iš D_3 einama į L; lobis surastas, 
5. iš L einama į D_3, patenkama į D_1, 
6. sprogdinama siena iš D_1 į U_1, 
7. einama iš D_1 į U_1, upė nuneša į U_4, 
8. išeinama iš labirinto.