 |
Az S. 33. feladat (2008. február) |
S. 33. Az interneten barangolva érdekes játékokra bukkanhatunk. Egy játékban például egy egységnégyzetekből felépített padlózaton egy 2×1×1 méretű téglatestet kell úgy elgörgetni a kezdőponttól a célig, hogy eközben a téglatest minden gördítés után teljesen alátámasztva maradjon (azaz teljesen a padlózaton feküdjön). A téglatest álló helyzetből indul, és álló helyzetbe is érkezik, tehát mindkét esetben valamelyik 1×1-es lapján áll. A gördítést tekintsük a téglatest padlózattal érintkező valamelyik éle körüli 90o-os forgatásként, a (felülről nézve) jobb oldali él körüli forgatást jelöljük J-vel, a felső körülit F-fel, és így tovább.
Írjunk programot, amely meghatározza, hogy egy adott pálya megoldható-e, azaz létezik-e a téglatestet a kezdő egységnégyzetből a végsőbe vivő gördítés sorozat. Ha igen, adjunk is meg egy legkisebb számú gördítésből álló megoldást. A program a pálya leírását fájlból olvassa, az eredményt fájlba írja. A bemeneti, illetve kimeneti fájlok nevei az első, ill. második parancssori argumentumok.
A bemenet első sora két, szóközzel elválasztott, egész számot: a pálya S szélességét és M magasságát tartalmazza (2
S,M100). Az ezt követő M sor mindegyike S számjegyet tartalmaz egymás mellé írva. Ha az adott mezőre nem terjed ki a padlózat, azaz oda nem kerülhet a téglatest, akkor ez az érték zérus. A kezdő- és végpozíciót a 2-es illetve a 3-as, a padló többi részét az 1-es számjegy jelöli.
Ha van megoldás, akkor a kimenet egyetlen sorában az J, F, B, L karakterek által kódolt gördítés sorozat, egyébként pedig a ,,Nem megoldhato.'' karaktersorozat szerepeljen.
Beküldendő a program forráskódja (s33.pas, s33.cpp, ...), valamint a program rövid dokumentációja (s33.txt, s33.pdf, ...), amely tartalmazza vázlatosan a megoldás leírását, és megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.
(10 pont)
A beküldési határidő 2008. március 17-én LEJÁRT.
A megoldás menete
Először is azt kell meggondolni, hogy miként írjuk le a téglatest pozícióját. Erre egy kézenfekvő megoldás, ha mindig azt nézzük, hogy az adott helyzetben melyik mezőn van a bal felső fele, és erről a mezőről (ha fekszik) merre lóg le. Tehát a téglatestnek van egy koordinátája (azé a mezőé, amin a bal felső fele van), és egy helyzete: áll, jobbra fekszik, lefelé fekszik. Vegyük észre, hogy ha például egy jobbra fekvő téglatestet jobbra gördítünk, x-koordinátája 2-vel növekszik.
Készítsünk egy G gráfot a következő módon: minden mezőhöz vegyünk fel három csúcsot, melyek jelentése: "az adott mezőn álló helyzetben", "az adott mezőn jobbra fekvő helyzetben", "az adott mezőn lefelé fekvő helyzetben". Majd minden csúcsot kössük össze azokkal a csúcsokkal, amelyekbe az adott csúcsban lévő téglatest egyetlen görgetéssel eljuttatható. Tehát pl. a ((x,y), álló helyzet) csúcsot az ((x+1,y), jobbra fekszik), ((x-2,y), jobbra fekszik), ((x,y+1), lefelé fekszik), ((x,y-2), lefelé fekszik) csúcsokkal. Az ábra a középső mezőn lévő álló (felül), jobbra (jobbra), lefelé (alul) helyzethez tartozó csúcsok szomszédait mutatja:
Ha a (kezdőpozíció, álló helyzet)-nek megfelelő csúcsot s-sel, míg a (végpozíció, álló helyzet)-nek megfelelőt t-vel jelöljük, akkor feladatunkat úgy is megfogalmazhatjuk, hogy a G gráfban egy legrövidebb utat keresünk s-ből t-be. Mivel azonban minden élsúly egységnyi, ez nem más, mint egy egyszerű szélességi keresés. Mivel egy konkrét útvonalat is meg kell adnunk, közben tárolnunk kell minden csúcsra azt is, hogy honnan jutottunk oda.
A szélességi bejárás műveletigénye , ahol p a gráf csúcsainak, e pedig éleinek száma. Esetünkben p=3.S.M, ugyanakkor tudjuk, hogy 1 csúcsnak legfeljebb 4 szomszédja van, hiszen legfeljebb 4 irányba léphetünk. Ezért e<=2p. Így az algoritmus műveletigénye
, a mezők számában lineáris (tárigénye úgyszintén).
Mintamegoldás
A C++ nyelven készült mintamegoldás letölthető az alábbi linkre kattintva:
Engedy Balázs
Statisztika:
2 dolgozat érkezett. 6 pontot kapott: 1 versenyző. 5 pontot kapott: 1 versenyző.
A KöMaL 2008. februári informatika feladatai