NézetNyomtat

15-ös játék (Megoldás)
Címkék > Feladat

15-ös játék

Forrás: Skiena, Revilla Programming Challenges
Valószínűleg mindenki találkozott már a 15-ös játék valamelyik változatával, ha nem is tudta, hogy ez a neve a játéknak. Egy $4 \times 4$-es táblán 15 tologatható négyzet alakú elem és egy üres hely található. A 15 elemnek van egy eredeti sorrendje (ami lehet egyszerűen egy számsor, de lehet egy kép is), majd "megkeverik" az elemeket. Feladatunk az eredeti sorrend visszaállítása. Az egyetlen megengedett lépés, hogy az üres helyre tolhatjuk valamelyik - az üres hellyel szomszédos - elemet.

Feladat

Egy adott táblára döntsük el, hogy megoldható-e a játék, és ha igen, adjunk meg egy megoldást.

Bemenet

A bemenet az elemek kezdeti elrendezését adja meg, négy sorban négy-négy szóközzel elválasztott számmal. A kirakós darabjait az 1, 2, ..., 15 számok jelzik, az üres helyet pedig a 0. A cél mindig az
 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15  0
állapot elérése.

Kimenet

Ha a feladvány nem oldható meg, a kimenet egyetlen sorába írjuk a következőt: "Nincs megoldás."
Ha megoldható, akkor adjunk meg egy lehetséges megoldást. A megoldást úgy kódoljuk, hogy az üres hely "mozgásának" irányát adjuk meg lépésenként. Fel - F, Le - L, Balra - B, Jobbra - J. A lépések kódját egyetlen sorba írjuk, szóközök nélkül.

Példa

15.be15.ki
2 3 4 0
1 5 7 8
9 6 10 12
13 14 11 15
BBBLJLJLJ
13 1 2 4
5 0 3 7
9 6 10 12
15 8 11 14
Nincs megoldás.

Olvasmány

Tesztadatok