Kezdőlap


Feladat:	S.4	Korcsoport: -	Nehézségi fok: -
Füzet:	2004/december, 556. oldal		PDF \| MathML
Témakör(ök):	Nehezebb feladat

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

A Sokoban nevű számítógépes játék egy négyzethálós pályán folyik, ahol $n$ darab ládát helyeztek el, ezeket a ‐ szintén $n$ darab ‐ megjelölt mezőre kell tologatnunk a pályán mozgó emberkével. Az emberke vízszintesen és függőlegesen, összesen négy irányban mozoghat. Minden lépéskor vagy szomszédos üres mezőre kell lépnie, vagy pedig egy ládát kell maga előtt arrébb tolnia. (Egy mezőre természetesen csak egy láda kerülhet.) Bizonyos mezők ,,falak'', ahova nem léphetünk és ládát sem tolhatunk.
Írjunk programot a játék megoldására. A program a standard bemenetről olvassa be a kiinduló állást. Az első sorban a pálya magassága és szélessége fog állni, az utána következő sorok a pálya sorai lesznek. A mezőket a következő karakterekkel kódoljuk:

\begin{matrix} # & Fal. Ide az emberke nem léphet és láda sem kerülhet. \\ $ & Láda. \\ szóköz & Üres mező \\ . & Megjelölt mező. Ide egy ládát kell majd tolnunk. \\ * & Láda egy megjelölt mezőn. \\ @ & Emberke \\ + & Emberke megjelölt mezőn \end{matrix}

A program keresse meg a legrövidebb lépéssorozatot, amellyel a ládákat a helyére tolhatjuk (ha több legrövidebb is van, akkor bármelyiket választhatja), és írja ki a standard kimenetre. Az első sorba írja a lépésszámot, a második sorba pedig a lépéseket. A lépéseket az F (fel), L (le), B (balra) és J (jobbra) karakterekkel kódolja. Ha nincs megoldás, akkor írja ki azt, hogy NINCS.
A pálya legfeljebb

15 \times 15

-ös lesz (a szélső sorok és oszlopok csupa falból fognak állni), a ládák száma legfeljebb

3

. A bemenetként kapott adatok mindig helyesek lesznek. Az outputon kívül más szöveget ne írjon ki a program.
Példa:

\begin{matrix} Input & Output \\ 6 7 & 14 \\ ####### & LJJBLLJFFLJJFB \\ #@#.### \\ #  *  # \\ # $ # \\ #     # \\ ####### \end{matrix}