Jill Bates
nem szeret hegyet mászni. Jill mindenhova kerékpárral
megy, de mindig a lehető legkönnyebb és legrövidebb utat igyekszik választani.
A jó hír az, hogy Jill Greenhillsben
lakik, ahol minden út egy derékszögű rács mentén épült ki. A Kelet-Nyugat
irányú utat utcának, az Észak-Dél irányú utat
sugárútnak nevezzük. Bármely két szomszédos kereszteződés távolsága egyenlő. A
rossz hír az, hogy Greenhillsben sok a hegy, és sok
az egyirányú utca. Jill az útvonal kiválasztásánál az
alábbi három szabályt alkalmazza.
1. Elkerüli a 10 méternél nagyobb emelkedést a szomszédos kereszteződések
(rácspontok) között!
2. Soha nem megy forgalommal szemben az egyirányú utcákban!
3. A lehető legrövidebb útvonalat választja!
Írjunk programot, amely segít Jillnek egy elfogadható útvonal megtalálásában!
Bemenet:
Az input állomány a következő formátumban
tartalmazza az adatokat:
ˇ
Az első sor két egész számot tartalmaz. Az első egész n; az utcák
száma, a második egész m; a sugárutak száma. (1<=n<=20, 1<=m<=20)
ˇ
A következő n sor a kereszteződések magasságait tartalmazza. Minden sor
egy utcát reprezentál, és pontosan m egészet tartalmaz. Ezek az egészek az
adott utcán lévő kereszteződések méterben mért magasságai.
ˇ
Ezek után egy vagy több sor következik, amelyek az egyirányú utcákat
definiálják. Minden ilyen definíció két pár egész számot tartalmaz, az utca
sugárút utca sugárút formátumban. Az első pár az utca kezdő-, a második
pár az utca végpontját definiálja. Minthogy Greenhills
egy szigorú négyzetrács szerint épült, ezért ha a két pont nem szomszédos,
akkor az utca a közbülső rácspontokon (útkereszteződéseken) is átmegy. Például
az
5 7 5 8
5 8 5 9
5 9 5 10
sorozat
reprezentálja az 5-7-től 5-8-ig, 5-8-tól 5-9-ig, 5-9-től 5-10-ig tartó
egyirányú utcákat. Az egyirányú utcák felsorolását négy darab 0 zárja a fenti
formátumban.
ˇ
Végül egy vagy több sor következik, amelyek mindegyike két rácspontot
tartalmaz az utca sugárút utca sugárút formátumban. Az első pár Jill útjának kezdő-, a második végpontjának koordinátái. Az
inputot négy darab 0 zárja.
Feltehetjük, hogy az utcák és sugárutak koordinátái
a fent definiált határok között vannak, valamint hogy az utak definíciói
szigorúan Észak-Dél, illetve Kelet-Nyugat irányúak.
Kimenet:
Az input állomány minden kezdőpont-végpont párjára
írassuk ki egy, a szabályoknak megfelelő útvonal rácspontjait! A rácspontot az
'utca-sugárút' formában írjuk ki, az egyes rácspontokat pedig a '->' karakterekkel kössük
össze! Ha Jill szabályainak több útvonal is megfelel,
akkor elegendő egyet kiíratnunk. Ha nincsen a szabályoknak megfelelő útvonal,
vagy a kezdőpont egybeesik a végponttal, akkor egy erre figyelmeztető szöveget
írassunk ki! Minden útvonalleírás után egy üres sornak kell szerepelnie!
Példa:
|
INPUT.TXT |
OUTPUT |
|
3 4 10 15 20 25 19 30 35 30 10 19 26 20 1 1 1 4 2 1 2 4 3 4 3 3 3 3 1 3 1 4 3 4 2 4 2 1 1 1 2 1 0 0 0 0 1 1 2 2 2 3 2 3 2 2 1 1 0 0 0 0 |
1-1->1-2->1-3->1-4->2-4->2-3->2-2 2-3->2-3: Maradj helyben! Nincs 2-2->1-1 út. |
(ACM döntő 1995)