Az S. 52. feladat (2010. március)

S. 52. Az ábra egy tavat ábrázol, amelyben egy kígyó rejtőzik. Az állat teste vízszintesen és függőlegesen tekereg, de saját magát még sarkosan sem érinti. A fekete mezők sziklák, melyeken a kígyó nem haladhat át. A táblázat alatti sorban lévő számok azt jelölik, hogy az adott oszlopban hány mezőben van kígyórész. A kígyó feje és farka adott, kilátszik a vízből.

Készítsünk programot, amely megadja, hogy a kígyó hogyan helyezkedik el a vízben. A program a parancssor első argumentumaként megadott bemeneti állománya a tó és a kígyó ismert adatait tartalmazza. Az első sor a négyzet alakú tó N (3N20) oldalhosszát, a kígyó M (3M) méretét, míg a második sor négy, szóközzel ellátott E₁, E₂, V₁ és V₂ egész száma (1E₁,E₂,V₁,V₂N) a kígyó fejének és farkának koordinátáját adja meg. A harmadik sor K (0KN) a vízben lévő sziklák számát, majd az ezt követő K darab sor mindegyike két egész számot, a sziklák koordinátáját tartalmazza. Az utolsó sor N darab számot tartalmaz, amelyek az oszlopok kígyórészeinek számát adja meg.

A parancssor második argumentumaként megadott kimeneti állomány N sorban a tavat, illetve a kígyó helyzetét jelenítse meg. A tó minden cellájának tartalmát három karakternyi helyre írjuk ki. A vizet szóközök, a kígyó testét a fejtől mért távolság ábrázolja.

Ha a feladatnak nincs megoldása, akkor a kimenet tartalma ,,Nincs megoldás'' legyen.

Beküldendő egy tömörített s52.zip állományban a program forráskódja (s52.pas, s52.cpp, ...), valamint a program dokumentációja (s52.txt, s52.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ó.

Tesztállományok: kigyoteszt.zip

A feladat ötletének alapja a Magyar logikai rejtvények weboldalról származik.

(10 pont)

A beküldési határidő 2010. április 12-én LEJÁRT.

Megoldásokról

Nagy Miklós (Győr, Révai Miklós Gimnázium) 11. osztályos tanuló megoldása alapján

A program a kígyó helyzetének megkereséséhez a visszalépéses keresés módszerét alkalmazza. A kígyó farkától visszafele haladva keresi meg a kígyó testének lehetséges helyzeteit.

A tó adatai a viz mátrixban vannak tárolva, melyben a számok jelentése a következő: 0- víz és 1- kő. A nagyobb számok a kígyó testét jelölik, méghozzá a kígyó fejétől mért távolság plusz 3-at. A plusz 3 a víztől és a kőtől való megkülönböztethetőséget szolgálja.

A keresés folyamán a kígyó farkától indulunk visszafele a fejéhez. A faroktól való indulás teszi lehetővé, hogy a kígyót a kövektől egyszerűbben tudjuk megkülönböztetni. A soron következő pont megkeresését a tekereg eljárás végzi. Ez addig keresi a lehetséges elhelyezéseket, amíg az 1-es sorszámú testdarab a fej pozíciójába kerül vagy amíg az összes lehetséges esetet végignézi (ha nincs megoldás). A következő testrész megkeresésénél 4 lehetséges eset van, ezek közül mindig a sorszám szerint első lehetséges lépést hajtja végre. A következő lépés feltételei: A kijelölt mező a tóban legyen és ne legyen kő. A kijelölt mező 8 szomszédja közül max 2 kígyórész lehet, és ez a két rész a fejtől mért távolságban is a két legközelebbi lehet, ellenkező esetben a kígyó érintené önmagát, ami a feladat szerint nem lehetséges. A lépendő oszlopba van-e még hely még egy résznek, az elején megadott testrészszámok szerint alapján?

Ha a lépés lehetséges, akkor végrehajtja, ha pedig egyik irányba sem tud tovább haladni, akkor visszalép az előző pozícióra és visszaállítja a pálya megfelelő értékeit.

Ha megvan a kígyó pozíciója, akkor kiírja azt a megadott célfájlba. s52.pas

Tesztállományok: k1.be k2.be k3.be

Statisztika:

13 dolgozat érkezett.
10 pontot kapott:	Adrián Patrik, Borsos 607 Zalán, Fekete 976 János, Mokcsay 026 Ádám, Nagy 111 Miklós, Weisz Ágoston, Weisz Gellért.
9 pontot kapott:	Éles András.
8 pontot kapott:	2 versenyző.
5 pontot kapott:	2 versenyző.
Nem versenyszerű:	1 dolgozat.

A KöMaL 2010. márciusi informatika feladatai