NézetNyomtat

Labirintus (Megoldás)
Címkék > Feladat
Elmélet > Algoritmusok > Gráfalgoritmusok
Versenyek > Nemes Tihamér OKSzTV > 2007 > Döntő > 11-13. osztály

Labirintus

Tekintsük azt a labirintust, amely egy $M\times N$-es négyzetrács, amelynek minden mezője le­het:
  • Üres (0)
  • Fal (1)
  • Kapcsoló (2)
  • Ajtó, amely vagy nyitva van (3), vagy zárva van (4)
Ha kapcsoló mezőre lépünk, akkor minden nyitott ajtó bezáródik, és minden zárt ajtó kinyílik. A labirintus $(1,1)$ koordinátájú bal felső sarkából a lehető legkevesebb lépéssel el kell jutni a jobb alsó $(M,N)$ koordinátájú mezőjére. Minden lépésben a szomszédos mezőre léphetünk balra, jobbra, lefelé vagy felfelé, feltéve, hogy az nem fal és nem zárt ajtó.

Feladat

Készíts programot (LABI.PAS, …), amely kiszámítja, hogy legkevesebb hány lépésben lehet kijutni a labirintusból, és meg is ad egy kivezető utat!

Bemenet

A LABI.BE szöveges állomány első sora két egész számot tartalmaz egy-egy szóközzel elválasztva, az első a labirintus sorainak $(2\le M\le 100)$, a második pedig a labirintus oszlopainak száma $(2\le N \le 100)$. A további $M$ sor mindegyike $N$ egész számot tartalmaz egy-egy szóközzel elválasztva. Az állomány $i+1$-edik sorában a $j$-edik szám a labirintus $(i,j)$ koordinátájú mező­jét adja meg, a fenti kódolás szerint.

Kimenet

A LABI.KI szöveges állomány első sor az egyetlen 0 számot tartalmazza, ha nem lehet ki­jutni a labirintusból, egyébként a kijutáshoz minimálisan szükséges lépések $K$ számát! A kö­vetkező sor pontosan $K$ karaktert tartalmazzon (szóközök nélkül), amely a kijutást eredménye­ző egy legrövidebb lépéssorozat! A balra lépés jele a B, a jobbra lépésé a J, a felfelé lépésé az F, a lefelé lépésé az L. Több megoldás esetén bármelyik megadható.

Példa

LABI.BE LABI.KI 
4 5				
0 4 2 1 0
2 2 2 3 0
1 0 4 3 1
0 0 1 0 0

9
LJLFJJLLJ

Tesztadatok

labirintus.zip