Az S. 55. feladat (2010. szeptember)

S. 55. Közismert, hogy egy huszárral be tudjuk járni a sakktábla összes mezőjét úgy, hogy minden mezőt pontosan egyszer érintünk. Erre könnyen megjegyezhető, egyszerű algoritmus áll rendelkezésre. A megoldandó feladat most ennél bonyolultabb. Az első néhány lépést már megtették helyettünk.

Írjunk programot, amely megkeresi a megkezdett út leghosszabb folytatását. A program első parancssori paramétere az eddigi utat tartalmazó fájl neve, a második parancssori paraméter pedig az út folytatását tartalmazó fájl neve. Mindkét fájl ugyanolyan szerkezetű, az első sor tartalmazza a tárolt lépések (L) számát, a második sorban pedig az érintett L darab mező következik egymástól egy-egy szóközzel elválasztva, a lépések sorrendjében.

[] A sakktábla mérete 6×6, a mezők jelölése a játékban megszokottnak megfelelő.

[] A bemeneti fájl utolsó felsorolt mezője és a kimeneti fájl első mezője egyezik.

[] Ha az út nem folytatható, akkor az első sorba az 1 kerüljön, a másodikba pedig az a mező, ahol a huszár éppen áll.

Beküldendő a feladat megoldását tartalmazó forrás és projektállományok (az .exe és más a fordító által generált kiegészítő állományok nélkül), valamint a megoldás menetét röviden bemutató dokumentáció (s55.txt, s55.pdf, ...) egy tömörített mappában (s55.zip).

(10 pont)

A beküldési határidő 2010. október 11-én LEJÁRT.

A beküldők többsége helyesen ismerte fel, hogy a backtrack algoritmust kell használni a megoldáshoz, mivel a maximális lépésszámot kerestük. A lényeg dióhéjban: - az eddig bejárt mezőket foglaltnak jelöljük - az utolsó pozícióból megpróbálunk továbblépni (a lehetséges "irányokkal" rögzített sorrendben próbálkozunk) - ha egy adott pozícióból nem vezet tovább út, akkor - ha a hozzá tartozó lépésszám maximális - az utat mentjük és visszalépünk az előző mezőre, ahonnan a következő iránnyal próbálkozunk. - a program befejeződik az összes lehetséges út bejárásakor, valamint akkor is, ha találtunk egy 36 lépés hosszú utat.

Sokan a kódolást is hiba nélkül végezték, a legtöbb program a legtöbb tesztesetre egy-két másodperc alatt lefutott.

A következő teszteseteket használtuk az értékelés során:

- csak egy mezőn jártunk (be1) - 6 mezőt érintettünk, a tábla teljesen bejárható (be8) - 18 mezőt érintettünk, a tábla teljesen bejárható (be3)

- a táblát teljesen bejártuk, nincs továbblépésre mód (be2) - az út nem folytatható (be6)

- 12 mezőt érintettünk, a tábla nem járható be, de folytatható (be5) - 18 mezőt érintettünk, a tábla nem járható be, de folytatható (be4) - 25 mezőt érintettünk, a tábla nem járható be, de folytatható (be7)

A tesztesetek: s55teszt.zip

Sok hibátlanul működő megoldás született, az egyik legtömörebb megoldást Boros Zalán adta: s55borsos.cpp

Egy lehetséges kimenet: s55kimenet.zip

Statisztika:

17 dolgozat érkezett.
10 pontot kapott:	Adrián Patrik, Barta 111 János, Borsos 607 Zalán, Fekete 976 János, Mihálykó András, Nagy 111 Miklós.
9 pontot kapott:	Élő Dániel, Nagy Róbert, Paczolay Gábor, Weisz Gellért.
8 pontot kapott:	2 versenyző.
7 pontot kapott:	1 versenyző.
6 pontot kapott:	1 versenyző.
4 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2010. szeptemberi informatika feladatai