Programozás‎ > ‎Feladatok‎ > ‎

Kisvakond kalandjai

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