Programozás‎ > ‎Feladatok‎ > ‎

Tologatós játék

Egy N x N-es négyzet mezőire beírtuk 1-től (N2-1)-ig a számokat, egy mező pedig üresen maradt. A kitöltött mezők csempék, az üres hellyel szomszédos csempe az üres helyre tolható. Az a cél, hogy sorba rendezzük a csempéket: bal felülre kerül az 1-es, utána soronként következnek nagyság szerinti sorrendben a számok, és a jobb alsó mező üres.

Feladat

Írjunk programot, ami beolvas egy eredeti elrendezést, és megadja, hogy legkevesebb hány mozgatással oldható meg a feladat. Azt is meg kell tudnia állapítani, ha a feladatnak nincs megoldása. Ha pedig van, akkor ki kell írni a minimális lépésszámot, és meg is kell adni a lépéseket.

Bemenet

A bemenet első sora N értékét tartalmazza, ami legalább 2 és legfeljebb 10. Ezután N sorban a mezők következnek, szóközökkel elválasztva. Az üres mezőt 0-val jelöljük.

Kimenet

Az első sorba a legrövidebb megoldás lépésszámát kell írni, utána pedig a megoldás lépéseit (a teljes tábla kiírásával). Az eredeti táblát is írjuk ki, és a lépéseket kötőjellel ("-") válasszuk el egymástól. Ha nincs megoldás, akkor írjuk ki: "LEHETETLEN".

Példa

Bemenet  Kimenet
2
2 0
1 3
3
2 0
1 3
-
0 2
1 3
-
1 2
0 3
-
1 2
3 0
-


Tesztadatok

A puzzlexy.txt minimálisan xy lépésben oldható meg.

Címkék

A feladat forrása: Coursera, Algorithms I., Robert Sedgewick, Kevin Wayne
Algoritmusok: visszalépéses keresés, nyers erő, "best first search"