Az I. 265. feladat (2011. április)

I. 265. Valószínűleg mindenki ismeri a 15-ös játékot, ahol egy 4×4-es táblán 15 tologatható négyzet alakú elem és egy üres hely található. A játék során erre az üres helyre lehet a szomszédos elemek egyikét betolni. A 15 elemnek van egy helyes sorrendje, amely az értékek sorfolytonos növekvő elrendezését jelenti.

Az eredeti változat tehát 4×4-es tábláról szól, de változatlan szabályok mellett játszhatnánk N×M méretű táblán is.

Készítsünk programot, amely az N×M tábla eredeti állapotát helyreállító lépéssorozatot adja meg. A program első paramétere a bemeneti fájl, a második paramétere a kimeneti fájl neve legyen.

A bemeneti fájl első sora az N20 és M20 értékét tartalmazza, egymástól egyetlen szóközzel elválasztva. Az ezt követő N sor mindegyikében M darab szám található, egymástól pontosan egy szóközzel elválasztva, amely egy összekavart állapotot ír le. Az üres helyet a 0 jelöli.

A kimeneti fájl első sora az eredeti állapot helyreállításához szükséges -- nem feltétlenül minimális -- lépésszám legyen, a második sorban pontosan ennyi karakter szerepeljen. Minden karakter azt az irányt írja le, amely felé az üres helyre egy elemet tolunk. (B -- balról, F -- fentről, J -- jobbról, L -- lentről). Amennyiben a helyes sorrend a szabályos lépésekkel nem alakítható ki, az első sorban -1 szerepeljen.

Beküldendő egy tömörített i265.zip állományban a program forráskódja (i265.pas, i265.cpp, ...), valamint a program rövid dokumentációja (i265.txt, i265.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.

(10 pont)

A beküldési határidő 2011. május 10-én LEJÁRT.

A feladat jóval nehézséget okozott, mint vártuk: a beküldők egyike sem adott a tesztesetek mindegyikére működő megoldást.

Ketten is utaltak egy működőképes algoritmusra, amely a soronként az első M-1 elemet; a sor utolsó elemét; majd az utolsó két sor elemeit oszloponként teszi helyre. Ezeket elemi lépésekre, az üres helyek tologatására, illetve az üres helyet kezdetben a sarkában tartalmazó téglalap körvonalának forgatására bontották.

A megvalósításba azonban hiba csúszott, ezért a tesztesetek többségében nem kaphattak pontot a versenyzők.

Az értékelésnél használt tesztesetek: i265teszt.zip

Statisztika:

3 dolgozat érkezett.
5 pontot kapott:	1 versenyző.
3 pontot kapott:	1 versenyző.
2 pontot kapott:	1 versenyző.

A KöMaL 2011. áprilisi informatika feladatai