ACM RTK - 1. skupina

znajdi.se

Razvili smo nov iskalnik znajdi.se, ki nam izpiše, kako pridemo iz točke A v točko B. Problem je, da nam iskalnik korake izpiše v pomešanem vrstnem redu. Tako se opis poti iz kraja G v kraj S glasi:

GS
- mimo O nadaljujemo skozi tri križišča, dokler ne pridemo do A
- pri B zavijemo desno, dokler ne dospemo do S
- iz A zavijemo v krožno križišče, od tam nadaljujemo naravnost do D - na H zavijemo desno proti O
- od D sledimo modrim oznakam, dokler ne zagledamo B
- nato pri J peljemo naprej 1,2 km proti H
- iz G zavijemo levo proti J

Na srečo veljajo naslednje omejitve, ki nam bodo prišle prav pri urejanju navodil v pravi vrstni red:

• vsak korak poti (od enega kraja do naslednjega) je v svoji vrstici (ki je dolga največ 100 znakov) in v njej se ime kraja, pri katerem se ta korak začne, pojavi prej kot ime kraja, pri katerem se ta korak konča; to pa sta tudi edina dva kraja, ki sta v tej vrstici omenjena;
• ime vsakega kraja je ena sama velika črka angleške abecede (od A do Z — kot vidimo tudi v gornjem primeru);
• drugače se v navodilih velike črke ne pojavljajo (vsi drugi znaki so male črke, števke, ločila in presledki);
• imena vseh krajev so med seboj različna in v nobenega ne gremo več kot enkrat;
• pot se gotovo ne konča v istem kraju, v katerem se začne;
• vsaka vrstica (razen prve, ki vsebuje začetni in končni kraj) predstavlja en korak poti (v vhodnih podatkih torej ni kakšnih odvečnih vrstic, ki ne bi bile del iskane poti).

Napiši program, ki bo prebral začetni in končni kraj ter zmešana navodila. Tvoja naloga je, da izpišeš kraje na poti v pravilnem vrstnem redu. Če torej tvoj program prebere zgornja navodila in podatek, da želiš priti iz G v S, mora izpisati:

GJHOADBS

Tvoj program lahko podatke bere s standardnega vhoda ali pa iz datoteke pot.txt, karkoli ti je lažje.