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:

1. je zkonstrolováno, že cesta je cestou na zadané mapě podle definice,
2. je zkontrolováno, že cesta nejprve stoupá a pak klesá - má pouze jedno maximum a žádné dva body vedle sebe nemají stejnou nadmořskou výšku,
3. s referenčním řešením je srovnávána délka (length) cesty, která musí být “lepší nebo stejná” jako délka cesty nalezená referenčním řešením,
4. s referenčním řešením je konfrontováno stoupání cesty (gradient) podle definice.

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.

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.

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ř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$.

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.

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.

Vzhledem k variabilitě řešení nelze dodat očekávané výstupy - jak tomu bylo v předešlých úlohách. Výsledné řešení je hodnoceno podle zadaných parametrů - délka cesty, výška kopce a jeho sklon.

Další testovací soubory můžete získat vhodným přetočením testovacích map! Některé ze skrytých testů jsou vytvářeny právě pouhým přetočením veřejných testovacích map.

Například mapu z příkladu 3 lze testovat v několika variantách:

3 3
1 2 3
6 5 4
7 8 9

3 3
1 6 7
2 5 8
3 4 9

3 3
9 8 7
4 5 6
3 2 1

3 3
9 4 3
8 5 2
7 6 1

Doporučujeme napsat si pro testování jednoduchý skript, který Vám nové testovací sady vytvoří.

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

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 na mapě neexistuje.

3 3
1 2 9
2 1 2
3 2 5

Error: Cesta neexistuje!

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

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.

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]]}

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