Search
Stavební firma projektuje a staví lanovky v horách. Lanovky jsou určené převážně na zimní provoz, vozí lyžaře. Ti se pak spouští z kopců po sjezdovkách nebo i volně terénem.
Stavební firma dostane od zadavatele mapu kopce, na kterém má být lanovka postavena. Mapa je dána jako dvourozměrná matice velikosti $n \times m$ nadmořských výšek $a_{ij}, 1 ≤ i ≤ n, 1 ≤ j ≤ m$ jednotlivých bodů v terénu. Zadání je naprojektovat lanovku vedoucí přes kopec tak, aby její provoz byl minimální, tj. aby po své trase zbytečně neztrácela nadmořskou výšku a aby její celková délka byla minimální. Současně má firma navrhnout optimální trasy sjezdovek, které vzniknou na cestách vybudovaných pro výstavbu lanovek. Po cestách se bude vozit těžká technika, proto trasa opět nesmí zbytečně ztrácet výšku a vede delšími cestami v serpentinách. Tyto vlastnosti uvítají i lyžaři, kteří budou cesty využívat pro sjezd.
Cesta přes kopec je definována jako posloupnost nadmořských výšek bodů $v_1,v_2,…,v_k$, kde $v_1 = a_{1, 1}$ a $v_k = a_{n, m}$. Současně existuje index $z$, $1 ≤ z ≤ k$ takový, že platí $v_1<⋯<v_z$ a $v_z>⋯>v_k$. Snahou je, aby hodnota nadmořské výšky $v_z$ byla maximální možná.
Stoupání, resp. klesání cesty je definováno jako $S_u = \mathop{\text{max}} \{ | v_{i} - v_{i - 1} |, 1 < i ≤ z \}$, resp. $S_d = \mathop{\text{max}} \{ | v_{i} - v_{i - 1} |, z < i ≤ k \}$. Sklon cesty přes kopec definujeme jako maximum stoupání a klesání cesty - $S = \mathop{\text{max}} \left( S_u, S_d \right)$.
Lanovka (lift) vyžaduje nejkratší cestu přes kopec, která má maximální sklon, tj. ze všech nejkratších cest hledáme tu, která má maximální sklon. Délka cesty je dána rozměry matice a je rovna $n - 1 + m - 1 = n + m - 2$.
Sjezdovka (piste) je vedena nejdelšími cestami přes kopec s minimalizací sklonu cesty (s minimalizací maximálního sklonu svahu), tj. ze všech nejdelších cest hledáme tu, která má minimální sklon $S$.
Řešení úlohy může být i více
Viz příklad 3 (lift).
Pokud je víc stejných řešení úlohy, jsou všechna řešení vyhodnocovacím skriptem vyhodnocena jako správná. Vyhodnocení probíhá v několika krocích:
Na vstupu (čteme ze standardního vstupu) je dvourozměrná matice nadmořských výšek jednotlivých bodů v terénu. Na prvním řádku vstupu jsou dvě čísla n a m – rozměry matice. Následuje n řádků s m hodnotami – jednotlivé prvky matice. Pokud při čtení vstupu zjistíte chybu, vypište na standardní chybový výstup zprávu Error: Chybny vstup! a program ukončete s návratovou hodnotou 1.
n
m
Error: Chybny vstup!
1
Program může mít jeden z argumentů:
lift
piste
Pokud program argument nemá, vyhledá cestu pro lanovku i sjezdovku, postupně za sebou.
Pro každou nalezenou cestu je výsledek vypsán na dvou řádcích:
Pokud cesta na mapě neexistuje, vypíšte na standardní chybový výstup zprávu Error: Cesta neexistuje! a program ukončete s návratovou hodnotou 1.
Error: Cesta neexistuje!
Je zřejmé, že pro řešení úlohy je potřeba prohledat mapu do šířky. S využitím rekurze to může být s ohledem na hloubku rekurze problém. Proto se zde uplatní dynamické programování a princip memoizace, kdy si jednou vypočtené údaje pamatujeme a nepočítáme je opakovaně.
V úloze je zadána matice nadmořských výšek. Pokud vypočteme cestu pro lanovku (sjezdovku) do nějakého bodu, tuto informaci je dobré si pamatovat. K tomu využijeme dvourozměrné pole. Přemýšlejme nejprve, jaké údaje je nutné si pamatovat:
Podle postupu řešení může být dobré si pamatovat i více údajů.
Jakým způsobem budeme jednotlivé prvky matice počítat?
Zde je dobré si uvědomit, která “políčka” dvourozměrného pole mohou ovlivnit výsledek na místě (indexu) $[i][j]$ (i je číslo řádku, j číslo sloupce).
Při hledání cesty pro lanovku lze zjistit, že pro výpočet hodnot na místě $[i][j]$ v dvourozměrném poli je potřeba znát hodnoty na indexech $[i - 1][j]$ a $[i][j - 1]$. Situaci si nakreslete a přemýšlejte, jak to ideálně zařídit, abychom při výpočtu hodnoty $[i][j]$ znali hodnoty, které potřebujeme.
Při hledání cesty pro sjezdovku je situace obtížnější. Výpočet hodnoty na místě $[i][j]$ se může měnit až do doby, dokud nejsou vypočteny všechny okolní hodnoty $[i - 1][j]$, $[i + 1][j]$, $[i][j - 1]$, $[i][j + 1]$. Tak by ale výpočet mohl běžet do nekonečna. Je proto dobré si uvědomit několik skutečností:
Jak ovlivní předchozí “políčka” dvourozměrného pole hodnotu na místě (indexu) $[i][j]$?
Při hledání cesty pro lanovku se délka cesty se při přechodu z políčka $[i - 1][j]$, resp. $[i][j - 1]$ na políčko $[i][j]$ zvýší o jedničku. Sklon cesty upravíme podle aktuální hodnoty sklonu na políčkách $[i - 1][j]$ a $[i][j - 1]$ a sklonů mezi body $[i - 1][j]$, resp. $[i][j - 1]$ a $[i][j]$.
Při hledání cesty pro sjezdovku postupujeme obdobně, akorát musíme projít všechny sousedy bodu $[i, j]$, tj. body $[i - 1][j]$, $[i][j - 1]$, $[i + 1][j]$ a $[i][j + 1]$. Jejich parametry se v průběhu výpočtu mohou měnit, indikaci změny je vhodné si pamatovat, například ukládáním bodů do fronty.
Výslednou délku cesty a nejvyšší bod zahrneme do výpočtu až po vyřešení problému hledání cesty do a z kopce.
Délka cesty
Na mapě rozměrů $3 \times 3$ lze vidět rozdíl v cestě pro lanovku (obrázek vlevo) a sjezdovku (obrázek vpravo). Modré šipky znázorňují cestu nahoru, červené cestu dolů.
Optimální cesta pro lanovku má délku $5$ a vede přes vrcholy 1 8 9 6 5. Možná je i varianta 1 2 9 6 5, protože stoupaní na obou cestách je stejné - první případ $8 - 1 = 7$, druhý případ $9 - 2 = 7$.
1 8 9 6 5
1 2 9 6 5
Cesta pro sjezdovku se točí kolem celého kopce, její délka je $13$ a vede postupně přes vrcholy 1 2 3 4 5 6 7 8 9 8 7 6 5.
1 2 3 4 5 6 7 8 9 8 7 6 5
Nejvyšší bod cesty
Na mapě rozměrů $5 \times 4$ lze opět vidět rozdíl v cestě pro lanovku (obrázek vlevo) a sjezdovku (obrázek vpravo). Pokud cesta pro lanovku vede nejvyšším bodem, cesta pro sjezdovku se snaží být co nejdelší, a proto nejvyšší bod s výškou $20$ obchází.
Nakonec ani lanovkou se nemusíme dostat na nejvyšší bod mapy (nadmořská výška $200$), pokud by daná cesta přes nejvyšší bod vůbec neexistovala.
Testovací soubory z obrázků najdete zde.
Testovací soubory najdete zde.
Jediná neustále stoupající cesta na kopec. Všechny ostatní cesty vedou po rovině (1 1 nebo 2 2).
3 3 1 2 3 1 2 4 1 2 5
5 1 2 3 4 5
3 3 1 2 3 2 3 4 3 4 5
Pro sjezdovku je má cesta stoupání 1 a je nejdelší možná.
3 3 1 2 3 6 5 4 7 8 9
5 1 6 7 8 9
5 1 2 3 4 9
9 1 2 3 4 5 6 7 8 9
3 3 1 2 3 6 5 7 8 9
3 3 1 2 3 6 5 5 5 5 7 8 9
3 3 1 2 3 2 3 2 3 2 1
5 1 2 3 2 1
Cesta je v obou případech vybrána proto, že vede nejvýš, do nejvyššího bodu.
3 3 1 2 3 2 4 2 3 2 1
5 1 2 4 2 1
Cesta pro lanovku má nejvyšší stoupání i klesání ( 5 - 2 = 3). Naopak cesta pro sjezdovku stoupání i klesání minimalizuje (stoupání i klesání je 2).
3 3 1 3 5 2 5 3 4 2 1
5 1 2 5 2 1
5 1 3 5 3 1
Cesta na mapě neexistuje.
3 3 1 2 9 2 1 2 3 2 5
3 3 1 2 7 4 3 8 5 6 9
5 1 2 3 8 9
5 1 2 7 8 9
7 1 2 3 4 5 6 9
3 4 1 2 3 3 2 6 3 2 3 4 2 1
6 1 2 6 3 2 1
8 1 2 3 4 6 4 2 1
Cesta pro lanovku maximalizuje stoupání, které je v obou případech 3. Naopak cesta pro sjezdovku minimalizuje stoupání, které je nakonec 2.
5 5 2 3 4 6 10 3 4 5 6 11 4 5 7 9 12 7 8 9 10 12 10 9 8 13 14
9 2 3 4 7 8 9 10 13 14
9 2 3 4 5 6 9 10 13 14
9 2 3 4 5 7 9 10 12 14
5 5 2 4 15 8 10 7 8 14 18 20 9 6 13 21 24 10 11 12 15 17 28 7 8 10 12
9 2 7 8 14 18 21 24 17 12
13 2 7 9 10 11 12 13 14 18 21 24 17 12
V tomto a dalších příkladech může být řešení i více, rozhodující je délka cesty a její sklon (stoupání, resp. klesání). Pokud vám vychází jiná řešení, zkontrolujte si tyto parametry cesty.
5 5 2 4 6 8 10 12 14 16 14 12 23 24 25 11 19 21 22 24 17 15 1 3 5 7 9
9 2 12 23 24 25 24 17 15 9
13 2 4 6 8 10 12 14 16 25 24 17 15 9
8 8 1 15 14 13 12 11 10 9 2 16 24 23 22 21 20 8 3 17 25 32 30 29 19 7 4 18 26 33 32 28 18 6 5 19 27 34 31 27 17 5 6 20 28 29 30 26 16 4 7 21 22 23 24 25 15 3 8 9 10 11 12 13 14 2
15 1 2 3 4 5 19 27 34 31 27 17 5 4 3 2
65 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 33 32 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2
Pro lanovku i sjezdovku existuje více možných výstupů.
Příklad 14 - kopec_2_06
Vstup: Kopec velikosti 10×10.
Příklad 15 - kopec_2_07
Vstup: Kopec velikosti 15×20.
Příklad 16 - kopec_2_08
Vstup: Kopec velikosti 20×30.
Dále je řešení testováno na datech větších velikostí - kopce velikosti až $ 200 \times 300$ bodů.
Při řešení úlohy - viz příklad 1 (lift) lze pro cestu nahoru získat například (viz popis algoritmu):
{[0, 0, [0, 0]], [1, 1, [0, 0]], [2, 1, [0, 1]], [0, 0, [0, 0]], [1, 1, [1, 0]], [3, 1, [0, 2]], [0, 0, [0, 0]], [1, 1, [2, 0]], [4, 1, [1, 2]]}
Odpovídající matice pro cestu dolů obsahuje v tomto případě samé nuly.
Z matice je zřejmé, že délka maximální cesty je 4. Z odpovídajícího prvku matice na indexu [2, 2] lze dále zjistit, že maximální sklon cesty je 1 a předchozím bodem cesty je bod [1, 2]. Cesta pro lanovku do bodu [1, 2] má délku 3 (logicky o jedničku menší), sklon je stejný a předchozím bodem je bod [0, 2]. Takto pokračujeme při rekonstrukci cesty až do bodu [0, 0].
Matici konstruujeme postupně z bodu [0, 0] pro cestu nahoru a z bodu [n - 1, m - 1] pro cestu dolů. Stanovíme podmínky pro konstrukci “následujících” bodů matice. Hlavní podmínkou je neustále stoupající nadmořská výška a pak sklon svahu podle zadání úlohy.
[x, y]
[x + 1, y]
[x, y + 1]
Při řešení úlohy - viz příklad 11 (lift) lze pro cestu nahoru získat například následující matici:
{[0, 0, [0, 0]], [1, 1, [0, 0]], [2, 1, [0, 1]], [0, 0, [0, 0]], [1, 1, [0, 0]], [2, 4, [1, 0]], [0, 0, [0, 0]], [0, 0, [0, 0]], [2, 1, [1, 0]], [3, 1, [2, 0]], [0, 0, [0, 0]], [0, 0, [0, 0]]}
Odpovídající matice pro cestu dolů vypadá pak následovně:
{[0, 0, [0, 0]], [0, 0, [0, 0]], [0, 0, [0, 0]], [2, 1, [1, 3]], [0, 0, [0, 0]], [3, 3, [1, 2]], [2, 1, [1, 3]], [1, 1, [2, 3]], [0, 0, [0, 0]], [2, 2, [2, 2]], [1, 1, [2, 3]], [0, 0, [0, 0]]}
Vidíme, že vrcholem cesty je bod [1, 1] a celková délka cesty je 5 (cesta prochází přes 6 bodů). Stejnou délku cesty lze získat i v bodě [2, 1], tam je ale menší sklon cesty - ve směru nahoru i ve směru dolů.
Při řešení úlohy - viz příklad 11 (piste) lze pro cestu nahoru získat například následující matici:
{[0, 0, [0, 0]], [1, 1, [0, 0]], [2, 1, [0, 1]], [0, 0, [0, 0]], [1, 1, [0, 0]], [4, 2, [2, 1]], [0, 0, [0, 0]], [0, 0, [0, 0]], [2, 1, [1, 0]], [3, 1, [2, 0]], [0, 0, [0, 0]], [0, 0, [0, 0]]}
{[0, 0, [0, 0]], [0, 0, [0, 0]], [0, 0, [0, 0]], [2, 1, [1, 3]], [0, 0, [0, 0]], [3, 2, [2, 1]], [2, 1, [1, 3]], [1, 1, [2, 3]], [0, 0, [0, 0]], [2, 2, [2, 2]], [1, 1, [2, 3]], [0, 0, [0, 0]]}
Vrcholem cesty je opět bod [1, 1].
Java
Python
C/C++
Veřejné testovací soubory - DSA_HW04.
hill.py
Hill.java
hill.c
hill.cpp
clang -Wall -Werror -pedantic -std=c99 clang -Wall -Werror -pedantic -std=c+ +17
javac *.java java -classpath Hill
dynamické programování memoizace
20