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 |
Teszt #1 Teszt #2 |
(ACM regionális verseny 1997)