Kisvakond boldogan élt a négyzet alakú réten, és naponta meglátogatta barátját, akinek nem túl messze volt a vakondtúrása. Az idilli állapotnak a Város terjeszkedése vetett véget: a rét egy részét felparcellázták és szürke (téglatest alakú) házakat építettek a parcellákra. A zöld terület elvesztésén túl ez azért is fáj Kisvakondnak, mert így nehezebben tudja meglátogatni barátját.
Feladat
Írjunk programot, ami kiszámolja, mekkora utat kell megtennie Kisvakondnak, hogy barátjához érjen. A rét vakond-lépés oldalhosszúságú négyzetekre van bontva, és minden ház méretei egészek (vakond-lépésben), továbbá a házak pontosan illeszkednek a képzeletbeli négyzetrácsra. A rét M x M-es és Kisvakond nem hagyhatja el útja során.
A. változat: Kisvakond kénytelen kikerülni a házakat és élszomszédos négyzetekre tud lépni.
A távolságot vakond-lépésben kell megadni.
B. változat: Kisvakond beszerzett egy rúgós cipőt, amivel legfeljebb T egység távol tud ugrani, de csak akkor tudja használni, ha valami sima és szilárd felületről tud elrugaszkodni. Ezért ezzel a "járművel" a házak tetején tud ugrálni, ha azok elég közel vannak egymáshoz. Az ugrások mindig két egységnégyzet középpontja között történnek. (Saját vakondtúrásából úgy tud felugrani az első háztetőre, hogy a magasságkülönbséget nem kell figyelembe venni.)
A távolságot az ugrások számában kell mérni, mert az az igazán megerőltető. Tehát egy háztetőn Kisvakond átsétálhat arra a "mezőre" ahonnan a legközelebb van a következő háztető, ahova át szeretne ugrani, és a séta nem számít bele az út hosszába.
Bemenet
A bemenet első sorában a rét oldalának M hossza és az ugrás maximális T hossza található (10<= M <= 100, 2<= T <=10). A következő sorban Kisvakond és barátja otthonának koordinátái vannak megadva. Mindegyik koordináta 1 és M közötti egész, és a két otthon különböző négyzetbe esik. A következő sor a felépített házak számát adja meg (1<= H <= 50). Ezután H sorban a házak "bal alsó" és "jobb felső" koordinátái olvashatók. (A bal alsó sarok az (1,1), a jobb felső a (M, M).) Feltehetjük, hogy a házak nem fedik át egymást, sőt faluk sem érhet össze, de az előfordulhat, hogy a sarkuk összeér. Feltehetjük, hogy a két vakondtúrásra nem épült ház.
Kimenet
Az első sorba az A. változat, a másodikba a B. változat megoldását kell írni. Ha a házak miatt Kisvakond nem tud eljutni barátjához, akkor egy 0-t kell kiírni.
Példák
| Bemenet |
Kimenet |
10 2
1 1 10 10
8
1 2 1 4
1 6 2 9
4 6 4 7
5 4 9 5
6 8 7 10
10 3 10 3
9 7 10 7
9 9 9 10
| 20
7
|
100 10
1 1 100 100
2
51 50 100 50
49 52 49 100
| 198
0
|
Ábra az első példához:
Tesztadatok
A fenti táblázatban lévő adatokkal teszteltük a programokat.
Címkék
A feladat forrása: saját feladat
Algoritmusok: legrövidebb út súlyozatlan gráfban
2004-2016 BDG algoritmus szakkör
