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"
2004-2016 BDG algoritmus szakkör