Kitalálni egy labirintusból népszerű probléma a számítógépek számára. Ebben a feladatban a labirintus négyzet alakú cellák derékszögű tömbjéből áll; a cellák mindegyikét fal határolja az észak, dél, kelet és/vagy nyugat irányból. A cellák egyike a 'start' címkével, egy másik a 'cél' címkével lesz azonosítva. Írjunk programot, amely megtalálja e cellák közt az egyetlen lehetséges útvonalat, valamint megjelöli a cellákat az ezen az úton szereplő sorszámaikkal! A programnak meg kell jelenítenie a labirintust is, valamint meg kell jelölnie azokat a cellákat is, amelyeket a meglátogattunk, bár nem szerepelnek a start->cél úton! Az algoritmusnak az alábbi elveket kell követnie! Képzeljük el, hogy egy robot áll a start cellában! A robot előbb nyugati irányba próbál menni, majd északra, majd keletre, majd délre. A robot akkor tud a választott irányba lépni, ha
(a) nincs fal, ami útját állná,
és
(b) még nem volt az adott irányba eső következő cellában.
Ha a robot eléri a cél cellát, akkor útja véget ér. Ha olyan cellába ér, amiből nem tud továbbmenni, akkor visszafordul az előzőleg látogatott cellába, és a következő kipróbálatlan irányba indul. Tekintsük az alábbi ábrán látható bal oldalt látható labirintust! Ez két cella magas, három cella széles. A startot 'S', a célt 'C' jelöli. A robot először nyugatra (balra) próbál elindulni, de falat talál. Ezután északra (felfelé) próbál menni, de ismét fal blokkolja. Keleti (jobb) irányból is fal akadályozza, így végül dél felé indul el. Az új cellából csak kelet felé mehet. Innen ismét a leírt algoritmus alapján próbál utat találni. Előbb nyugati irányba próbál elindulni, de ott már volt, így észak felé veszi útját, sikeresen. Sajnálatos módon a következő cellából nem tudja folytatni útját, így visszatér a korábban már látogatott cellába. Most keletre próbál elmozdulni, és ez sikeres. Az új cellából északra indul, és eljut a célig. A labirintust az alább látható módon kell kiíratni. A start cellát '1' címkével kell megjelölni, a start->cél úton szereplő cellákat az úton szereplő sorrendben kell címkézni! A látogatott, de az úton nem szereplő cellákat kérdőjellel kell megjelölni!
|
+-+-+-+ |
+-+-+-+ |
Tekintsük a labirintust cellák tömbjének; a sorokat északról délre, az oszlopokat nyugatról keletre sorszámozva! A fenti labirintusban a start cella az első sor első oszlopában található, a cél cella az első sor harmadik oszlopában. Az input több adatsort is tartalmazhat. Minden labirintus leírását hat egészet tartalmazó sor kezdi. Az első két egész a magasságot (sorok száma) és szélességet (oszlopok száma) adja meg. A következő két egész a start cella pozícióját (sor és oszlop számát), az utolsó két egész a cél cella pozícióját adja meg. Minden labirintus legfeljebb 12 sort, és 12 oszlopot tartalmaz, és mindig van út a start és cél cellák között. Az első sort követően minden cellát egy egész számmal jellemzünk a labirintus sorainak sorrendjében. Ez a szám 1, ha a cellát keletről fal zárja le, a szám 2, ha a cellát délről fal zárja le, a szám 3, ha a cellát keletről és délről is fal határolja. Ha a cellát sem keletről, sem délről nem zárja le fal, akkor a szám 0. A labirintus szélén lévő cellák megakadályozzák, hogy a robot elhagyja a labirintust, bár e falak nincsenek specifikálva az inputban. Az utolsó labirintus leírását hat darab 0 követi.
Kimenet:
Minden labirintusra jelenítsük meg a labirintust úgy, hogy ahogy ez a fenti példában, illetve a lenti minta outputban látható! A labirintusokat előzze meg azok sorszáma! A sorszámozást 1-től kezdjük!
Példa:
|
INPUT.TXT |
OUTPUT.TXT |
|
2 3 1 1 1 3 |
Labirintus 1 Labirintus 2 |
(ACM regionális verseny 1997)