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) jsou vedeny 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.

Co si představit pod “ve směru do kopce vpravo”?

Řeka teče z kopce a každý vodák ví, že její levý břeh je ten, který je vlevo, když se díváme po proudu řeky, směrem z kopce. Když se otočíme proti proudu řeky, stane se tento břeh z našeho pohledu pravým. Pokud tedy kráčíme do kopce, volíme cestu vpravo. Tato cesta leží ve směru do kopce vpravo.

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.

Program může mít jeden z argumentů:

• lift – pro vyhledání cesty pro lanovku,
• piste – pro vyhledání cesty pro sjezdovku.

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:

• délka cesty $k$,
• posloupnost $v_1,v_2,…,v_k$ nadmořských výšek bodů cesty.

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:

• délku cesty do daného bodu,
• maximální/minimální sklon cesty do daného bodu,
• předchůdce daného bodu - cestu budeme muset zpětně rekonstruovat.

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í:

• Nemusíme nutně prohledávat všechny čtyři směry, stačí prohledávat ty, z nichž se do bodu $[i][j]$ dostaneme z bodu s nižší nadmořskou výškou.
• Body, které se mohou průběžně měnit, je vhodné si pamatovat, například ve frontě.

Jak ovlivní přechozí “políčka” dvourozměrného pole hodnotu na místě (indexu) $[i][j]$?

Při hledání cesty pro lanovku leží je mezi políčky $[i][j]$ a $[i - 1][j]$ vztah ve směru do kopce víc vpravo, tj. toto políčko $[i - 1][j]$ má na hodnotu údajů pro $[i][j]$ větší vliv.

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 je obtížnější definovat vztah ve směru do kopce víc vpravo. Okolní body lze například prohledat v pořadí $[i - 1][j]$, $[i][j - 1]$, $[i + 1][j]$ a $[i][j + 1]$. Dá se předpokládat, že první dva body budou ležet níž, než bod $[i][j]$ a zbývající body procházíme ve směru zprava vlevo. Ohledně délky a sklonu cesty platí stejná pravidla jako pro cestu lanovkou.

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.

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

5
1 2 3 4 5

Pro lanovku má uvedená cesta stoupání 5 a vede nejvíc vpravo. Cesta 1 2 3 4 9 má také stupání 5, ale vede více vlevo.

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

9
1 2 3 4 5 6 7 8 9

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

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 pro lanovku maximalizuje stoupání a navíc vede víc vpravo. Cesta 2 3 4 5 7 9 10 13 14 by měla stejné stoupání ale vede více vlevo. 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 7 9 10 12 14

Příklad 14 - kopec_2_06

Vstup: Kopec velikosti 15×20.

Příklad 15 - kopec_2_07

Vstup: Kopec velikosti 20×30.

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.

Při řešení úlohy - viz příklad 9 (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 9 (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]]}

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, 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].

Veřejné testovací soubory - DSA_HW04.

clang -Wall -Werror -pedantic -std=c99
clang -Wall -Werror -pedantic -std=c+ +17

javac *.java
java -classpath Hill

dynamické programování
memoizace