ACM 1997

A Risk egy táblás játék, amelyben több játékos tesz kísérletet a világ meghódítására. A játéktábla egy képzeletbeli világtérkép, amely országokra van osztva. A játékosok lépéseik során hadseregeket helyeznek át valamely országból egy ezzel szomszédos országba. Ezt a tevékenységet az ország meghódításának nevezzük. A játék menete során valamennyi játékosnak az a célja, hogy hadseregével egy startországból valamely célországba jusson. Ehhez hódítások sorozatát kell végrehajtania. A játékos célja a közbülső országok megválasztása úgy, hogy a szükséges hódítások száma minimális legyen. Adott egy 20 országból álló játéktábla leírása; az országokat az első 20 pozitív egész számmal azonosítjuk. Írjunk programot, amely adott start- és cél-országokhoz kiszámítja a meghódítandó országok minimális számát. A programnak nem szükséges kiíratnia az országok azonosítóit, csak az elfoglalandó országok számát, beleértve a célállomást is. Például, ha a start és célországok szomszédosak, akkor a helyes válasz 1.

Bemenet:

Az INPUT.TXT fájl a játéktáblák sorozatának leírásait tartalmazza. Egy játéktábla leírása 19 sorból áll. A leírás i és j azonosítójú országok szomszédságát csak akkor tartalmazza, ha i<j, ezáltal elkerüli a szomszédság kétszeri kódolását. A leírás i-edik sora (1<=i<=19) egy m egész számmal kezdődik; ez azt mutatja, hogy az i azonosítójú ország hány nagyobb azonosítójú országgal szomszédos. Ezután a sor még pontosan m darab számot tartalmaz; az i-vel szomszédos, i-nél nagyobb azonosítójú országok azonosítóit.
A leírás 20. sora egyetlen N egész számot tartalmaz (1<=N<=100), amely az ezután felsorolandó országpárok számát jelöli. A következő N sor mindegyike pontosan két egész számot tartalmaz, az első jelöli a start, a második a célország azonosítóját a lehetséges játékban. Az országok közt minden esetben lesz legalább egy út.
Az inpufájl több tábla leírását is tartalmazhatja. A programnak minden táblára, azon belül minden start és célországra meg kell határoznia a hódítandó országok minimális számát.

Kimenet:

Írjuk az eredményeket az OUTPUT.TXT nevű állományba! Az egyes játéktáblához tartozó eredmények felsorolását előzze meg egy "Teszt #T" alakú sor, ahol T az aktuális  tábla sorszáma, amely kezdetben 1. Az ezt követő Nt sor mindegyike kövesse a "start: i cél: j, lépések: k" formátumot, ahol i illetve j az aktuális start- és célországok, k pedig a meghódítandó országok minimális száma. Az egyes játéktáblákhoz tartozó eredményeket egy üres sorral kell lezárni.

Példa:
 

INPUT.TXT	OUTPUT.TXT
1 3 2 3 4 3 4 5 6 1 6 1 7 2 12 13 1 8 2 9 10 1 11 1 11 2 12 17 1 14 2 14 15 2 15 16 1 16 1 19 2 18 19 1 20 1 20 5 1 20 2 9 19 5 18 19 16 20 4 2 3 5 6 1 4 3 4 10 5 5 10 11 12 19 18 2 6 7 2 7 8 2 9 10 1 9 1 10 2 11 14 3 12 13 14 3 18 17 13 4 14 15 16 17 0 0 0 2 18 20 1 19 1 20 6 1 20 8 20 15 16 11 4 7 13 2 16	Teszt #1 start: 1 cél: 20 lépések: 7 start: 2 cél: 9 lépések: 5 start: 19 cél: 5 lépések: 6 start: 18 cél: 19 lépések: 2 start: 16 cél: 20 lépések: 2 Teszt #2 start: 1 cél: 20 lépések: 4 start: 8 cél: 20 lépések: 5 start: 15 cél: 16 lépések: 2 start: 11 cél: 4 lépések: 1 start: 7 cél: 13 lépések: 3 start: 2 cél: 16 lépések: 4

Az MBone a Multicast Backbone kifejezés rövidítése. Ez egy Internet Protokollra épülő virtuális hálózat megvalósítását jelenti. Szemben az adatok kapcsolatorientált átvitelével (unicast), valamint egy forrástól a hálózat minden tagjához való továbbításával (broadcast), az MBone gondoskodik a multicast lehetőségéről. Ez azt jelenti, hogy úgynevezett multicast csoportok jönnek létre. A csoport minden tagja képes adatok továbbítására és fogadására a csoporton belül.
Feladatunk az MBone egy egyszerűsített változatának modellezése. Modellünkben az MBone-t routerek és hostok alkotják. Minden host valamely routerhez tartozik. A router a hozzá kapcsolódó hostokkal szigetet alkot. A routerek kommunikációs csatornákon keresztül kapcsolódnak egymáshoz. Ezeken a csatornákon az adatáramlás egyirányú.
A multicast csoporthoz történő csatlakozás céljából a hostnak egy üzenetet kell küldenie routerének, amely tartalmazza a csoport címét, amelyhez a host csatlakozni szeretne. Ezután a host megkapja az összes csomagot, amelyet ennek a csoportnak címeztek. A hostok csomagokat (üzeneteket) küldhetnek a multicast csoportoknak. Evégből a csomagot el kell küldenie a szigeten belüli routerhez. A routerek a kapott csomagokból másolatokat készítenek. A másolatokat a szigetről kimenő kommunikációs csatornákra küldik, majd az adott csoport szigeten belüli tagjainak is küldenek egy-egy példányt belőlük.
Az üzenetek terjesztése egy egész értékkel, az úgynevezett TTL (Time To Live) értékkel korlátozott. Minden csomaghoz tartozik egy TTL érték. Ha egy csomag valamely csatornán keresztül kerül továbbításra, akkor TTL értéke a csatornához tartozó küszöb értékével csökken. Az üzenet nem továbbítható olyan csatornán, amelynek küszöb értéke magasabb a csomag aktuális TTL értékénél.

Bemenet:

A program inputja MBone hálózatok leírásából áll. Minden egyes hálózat leírásának első részében a hálózat topológiája van definiálva, a második rész pedig a hálózatban zajló eseményeket tartalmazza.
Az első rész egy m egész számot tartalmazó sorral kezdődik (1<=m<=10). Az m a hálózatban lévő szigetek számát jelöli. Ha m értéke 0, akkor vége van az inputnak. A következő sorok az m darab sziget leírását tartalmazzák. A szigeteket leíró rész első sora tartalmazza a sziget routerének nevét (legfeljebb 20 karakterben), valamint a sziget leírásából hátralévő sorok számát. E sorok kétfélék lehetnek:

Hostot leíró sor:    H <host címe>
Csatornát leíró sor: T <küszöb> <cél neve>

A <host címe> és <küszöb> mezők pozitív egészek; az adott host címét (azonosítóját), valamint a csatorna küszöb értékét tartalmazzák. A <cél neve> a kommunikációs csatorna másik végén található sziget routerének nevét tartalmazza, amely mindig különbözik az aktuális router nevétől.

A leírás második részének első sora egyetlen egész számot tartalmaz, amely a hálózatban zajló események leírására szolgáló sorok száma. Ez a szám nem nagyobb, mint 1000. Minden ilyen sor valamely host egy tevékenységét írja le, és az alábbi formátumok valamelyikét követi.

Csatlakozás (join):  J <host címe> <csoport címe>
Elhagyás (leave):    L <host címe> <csoport címe>
Csomagküldés (send): S <host címe> <csoport címe> <csomag ID> <TTL>

A <csoport címe>, <csomag ID> és <TTL> mezők pozitív egészeket tartalmaznak; jelentésük nyilvánvaló. A routerek neve, a hostok címe, a csomagok azonosítója mind egyediek. A csomagok TTL értéke legfeljebb 1000. A hálózatban legfeljebb 50 host és 100 csatorna lehet, míg az egyidejűleg aktív csoportok száma legfeljebb 20. Minden olyan csoport aktív, amelynek legalább egy host tagja. A hostok nem kívánnak csatlakozni olyan csoporthoz, amelynek tagjai, illetve nem kísérelnek meg elhagyni olyan csoportot, amelyhez nem tartoznak.

Kimenet:

Minden hálózatra listázzuk ki a hostok által kapott csomagokat! ha valamely host egy csomagból több példányt is kap - különböző útvonalakon -, akkor csak a legmagasabb TTL értékűt tartja meg, hiszen az érkezett a "legrövidebb" útvonalon. Minden hálózat leírásánál előbb írjuk ki a hálózat sorszámát, ahogy ezt a példában is láthatjuk! Az ezt követő sorok mindegyike a

<host címe> <csomag ID> <TTL>

formátumot kövesse! Itt <host címe> annak a hostnak a címe, amelyik a <csomag ID> azonosítójú csomagot kapta, a fennmaradó <TTL> TTL értékkel. Az outputot rendezzük a <host címe>, azon belül a <csomag ID> mezők szerint, növekvő sorrendet követve! Minden hálózat leírása után egy üres sornak kell szerepelnie!

Példa:
 

INPUT.TXT	OUTPUT.TXT
3 Nuremberg 3 T 8 Munich H 3768 H 3669 Munich 6 H 721 H 722 H 723 T 6 Nuremberg H 857 T 9 Ulm Ulm 5 H 51225 H 51226 H 51227 T 15 Nuremberg T 9 Munich 14 J 51227 26 J 3768 27 J 723 26 J 3768 26 S 3768 26 1000 17 J 857 26 S 3768 26 320 16 J 722 26 L 857 26 S 51227 26 1001 37 S 723 26 533 5 L 51227 26 L 3768 27 L 723 26 0	Hálózat #1 722 533 5 722 1001 28 723 320 8 723 533 5 723 1000 9 723 1001 28 857 320 8 3768 320 16 3768 1000 17 3768 1001 22 51227 1000 0 51227 1001 37

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!
 

+-+-+-+ |S| |C| + + + + |     | +-+-+-+

+-+-+-+ |1|?|5| + + + + |2 3 4| +-+-+-+

Bemenet:

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 1 1 0 0 0 0 4 3 3 2 4 3 0 3 0 0 2 0 0 3 0 0 1 0 0 0 0 0 0 0	Labirintus 1 +-+-+-+ |1|?|5| + + + + |2 3 4| +-+-+-+ Labirintus 2 +-+-+-+ |? ?|?| + +-+ + |3 4 5| + +-+ + |2 1|6| + +-+ + |   |7| +-+-+-+