Programozás‎ > ‎Feladatok‎ > ‎

Gyalogtúra

Többnapos teljesítménytúrákat szervezünk Magyarországon. Mivel a több napon át tartó gyaloglás meglehetősen fárasztó, szeretnénk korlátozni az egy napra eső távot: egy nap alatt két olyan település között haladhat az út, amelyek távolsága légvonalban nem több, mint 20 km. (A légvonalban mért távolságnál sokkal hosszabb lehet a járható terepen megtett út.)

Feladat

Írjunk programot, ami megadja, hogy két kiválasztott település között legkevesebb hány nap kell a fenti feltételek mellett az út megtételéhez.

Bemenet

A bemenet első sora a tesztesetek számát adja meg (1<= T <= 30). Ezután minden sorban két település szóközökkel elválasztott neve következik. A nevek csak az angol ábécé nagybetűit tartalmazzák (elnézést kérünk azoktól, akik érzékenyek a helyesírásra, de így megspórolhatjuk az ékezetes karakterek használatából eredő nehézségeket). Feltehetjük, hogy olyan településneveket adtunk meg, amelyek szerepelnek adatbázisunkban.

Mindegyik tesztesethez ugyanaz a térkép tartozik ( magyarorszag.csv ), amelyben a települések neve szerint rendezve 3137 hely nevét és földrajzi koordinátáit olvashatjuk, az alábbi formátumban:

ABA 47.069552 18.517811
ABADSZALOK 47.455435 20.613825
ABALIGET 46.145204 18.099522
ABASAR 47.817653 20.013838
ABAUJALPAR 48.300298 21.258464
ABAUJKER 48.310026 21.196713
ABAUJLAK 48.406457 20.962218
ABAUJSZANTO 48.276449 21.236782
ABAUJSZOLNOK 48.381242 20.980977
...

Kimenet

Minden tesztesethez egyetlen sort kell kiírni. A sorok első eleme a szükséges napok száma (N) ezután N+1 település neve következik,
a legrövidebb út állomásai, beleértve a kiinduló települést és a célállomást is. Ha több különböző megoldás létezik, bármelyiket kiírhatjuk.

Példa

A táblázatban csak az olvashatóság kedvéért helyeztünk el üres sorokat.

tura.be tura.ki
3
BUDAPEST EGER
GYOR SZEGED
KISMAROS HEJCE
6 BUDAPEST MOGYOROD ASZOD ZAGYVASZANTO GYONGYOSOROSZI KISNANA EGER

15 GYOR TOLTESTAVA TAPSZENTMIKLOS VERTESKETHELY CSOKAKO PATKA SEREGELYES ADONY TASS SZABADSZALLAS IZSAK BUGACPUSZTA JASZSZENTLASZLO PUSZTASZER SZATYMAZ SZEGED

10 KISMAROS TERESKE TERENY MATRASZOLOS NEMTI VARASZO FARKASLYUK VADNA NYOMAR FORRO HEJCE

Tesztadatok

Kisebb bemenet: tura.be tura.ki
Nagyobb bemenet:

Címkék

A feladat forrása: saját feladat
Algoritmusok: szélességi bejárás