6. Aaaaaaaaa! vzorové riešenie

..I..   .#I..   ..I..   ##I##
#X#X#   ###X#   #.#X#   ..###

5 5 5
....#
###..
####.
...##
.####

2

5 5 1
.....
####.
####.
...##
.####

4

5 5 1
....#
###..
####.
.####
..###

7

5 4 5
....
###.
####
####
.###

Do tejto jaskyne sa liezt neoplati

Ako neriešiť úlohu

Pri prvom pohľade by sa mohlo zdať, že úlohu pôjde vyriešiť nejakým jednoduchým prehľadávaním do šírky, pri ktorom skúsime vždy najskôr spraviť krok doprava a doľava a potom kopať. Už z príkladov je však jasné, že to tak jednoduché nebude. Občas totiž môže byť najefektívnejšia možnosť (alebo jediná možnosť) vykopať v jednom riadku niekoľko súvislých kociek, aby sme aj v riadku pod ním mohli vykopať niekoľko ďalších kociek (pričom musíme stáť na predtým vykopaných políčkach), a tak ďalej – ako môžeme vidieť na treťom príklade.

Nestačí nám teda vedieť, ako sme sa na nejaké políčko dostali – dôležité je aj to, ktoré políčka sme cestou vykopali.

V jaskyni sa hodí dynamit

Takýto typ zadaní vedie k myšlienke dynamického programovania, ktorého princípom je, že riešime čiastkové problémy (napríklad ako najefektívnejšie sa vieme dostať na dané políčko) a tieto čiastkové riešenia využijeme na efektívne vyriešenie ďalších podproblémov, až po riešenie pôvodného problému (ako najefektívnejšie sa vieme dostať na políčko v spodnom riadku).

Kľúčovú úlohu zohráva takzvaný stavový priestor – definujeme si stav ako nejakú \(n\)-ticu podstatných informácií, pre každý možný stav potom vyriešime podproblém pomocou iných stavov. Množinu všetkých stavov nazývame práve stavový priestor. Priestor preto, že si ho zvykneme predstavovať \(n\)-rozmerný, s “osami”, ktoré tvoria jednotlivé prvky \(n\)-tice.

Implementujeme ho často ako \(n\)-rozmerné pole – tento prístup funguje, pokiaľ vieme, aké má celý priestor hranice v každej súradnici. Druhá možnosť je pamätať si dosiahnuté stavy v slovníku, tá sa zíde najmä vtedy, keď očakávame, že navštívime omnoho menej stavov, než všetky možné, a preto sa neoplatí vyrábať si veľké pole.

V naivnom nefunkčnom riešení by stav vyzeral ako dvojica súradníc políčka, na ktorom sa práve nachádzame. Stavový priestor by preto tvoril dvojrozmerné pole veľkosti šírka krát výška (teda rovnakého tvaru, ako jaskyňa). Pre každý stav by sme si pamätali najmenší počet kociek, ktoré bolo treba vykopať, aby sme sa do neho dostali.

Stavový priestor je užitočný koncept aj bez dynamického programovania – môžeme ho napríklad prehľadávať spomínaným BFS alebo použiť Djikstru. Pokiaľ však dokážeme vymyslieť takú reprezentáciu, že stavy ukladáme v poli, riešime jeden po druhom a máme istotu, že aktuálny stav závisí len na “predošlých” a nie na “nasledujúcich”, je najjednoduchšie proste prejsť postupne všetky stavy, a to sa nazýva Dynamické programovanie (DP).

Čo bude náš stav

Opäť si pre každý stav budeme pamätať najmenší počet kociek, ktoré treba vykopať, aby sme sa do neho dostali.

Ako sme zistili skôr, definovať stav len pomocou súradníc nestačí, treba vedieť aj to, ako sme kopali, kým sme sa na dané políčko dostali. Mohli by sme teda skúsiť stav reprezentovať ako (súradnica Y, súradnica X, voľné políčka v jaskyni). Keďže však jaskyňa môže mať až \(V \times S\) políčok, mohlo by existovať \(V \times S \times 2^{V \times S}\) stavov – rozhodne by sme teda nedokázali všetky reprezentovať v poli a časovo aj pamäťovo by bolo prehľadávanie priestoru veľmi neefektívne.

V takejto reprezentácií si toho pamätáme zbytočne veľa – vôbec nás totiž nemusí zaujímať, aké políčka sa nachádzajú v iných riadkoch, než je aktuálny riadok a riadok pod ním. Keďže sa nevieme pohybovať smerom dohora, všetky políčka v nižších riadkoch vyzerajú presne tak, ako pôvodná jaskyňa (zatiaľ sme ich nemohli vykopať) a všetky políčka vyššie sme už prešli (a poznáme najefektívnejší spôsob, ako sa cez ne dostať do aktuálneho stavu).

Ďalej si vieme všimnúť, že pokiaľ začneme v jednom riadku kopať, môžeme pokračovať v kopaní už len do jednej strany (cúvať) – nevieme už vykopané políčko preskočiť, môžeme len cezeň spadnúť o riadok nižšie (a vtedy v danom riadku kopať prestaneme).

Takisto nemá zmysel kopať prerušovane, pretože všetky políčka uvoľnené pred preskočenou kockou (prerušením kopania), by sme vykopali zbytočne – v ďalšom riadku sa cez nevykopanú kocku nevieme dostať a v neskorších riadkoch už budú tieto políčka príliš vysoko, aby čokoľvek ovplyvnili. Má teda zmysel kopať len jeden súvislý úsek.

Vďaka tomu si stav vieme definovať ako štvoricu (súradnica Y, súradnica X, začiatok vykopaného úseku v aktuálnom riadku, koniec vykopaného úseku). Tento stavový priestor vieme ešte zmenšiť, keď si uvedomíme, že:

1. každý úsek prestaneme kopať stojac na políčku, ktoré je na jednom jeho konci (teda stačí riešiť kopanie úsekov končiacich tesne pred políčkom, kde stojíme)
2. a zároveň nás na každom políčku vo vykopanom úseku zaujíma počet vykopaných kociek len v jednom smere (totiž aj tak budeme z aktuálneho políčka kopať len jedným smerom, pretože podľa 1. chceme, aby koniec kopaného úseku bol vedľa políčka, kde stojíme).

Dostaneme tak stavový priestor (súradnica Y, súradnica X, dĺžka vykopaného úseku, smer kopania) s rozmermi \(V \times S^2 \times 2\) (posledný prvok štvorice môže nadobúdať len dve hodnoty, preto sa do asymptotickej zložitosti nepočíta).

Ako môžeme prechádzať medzi stavmi

Tu by sme mohli zvoliť jednu z dvoch základných možností – pre každý stav vyriešiť buď ako najlepšie sa dá do neho dostať (prechádzaním predošlých stavov), alebo ako najlepšie sa dá dostať do iných stavov z neho (prechádzaním nasledujúcich stavov a prepisovaním ich hodnôt lepšími).

Keďže dosť stavov pravdepodobne bude nedosiahnuteľných, oplatí sa zvoliť si druhú možnosť, ktorá nám dovolí pri navštívení nedosiahnuteľného stavu (čo spoznáme napríklad tak, že si na začiatku do všetkých stavov priradíme väčšiu hodnotu, než kedy vieme dosiahnuť, napríklad \(V \times S\)) tento stav jednoducho preskočiť.

Teraz už treba len vymyslieť prechody medzi stavmi. Stav, v ktorom sa nachádzame nám vraví, že sme na súradniciach \(X, Y\) a smerom (doprava alebo doľava) je určite voľných (predtým vykopaných) \(Z\) políčok (voľných políčok tam samozrejme môže byť viac, než \(Z\), a zároveň nemáme garantované ani to, že tých \(Z\) políčok sa dá dosiahnuť, pretože v riadku nižšie môžu byť diery).

Pohyb bude teda vyzerať tak, že sa skúsime pohnúť doľava aj doprava tak ďaleko, kým to pôjde – teda kým bude na našom riadku vykopané alebo voľné políčko a v nižšom riadku nebude voľné políčko (cez ktoré by sme spadli). V každom navštívenom stave sa pokúsime aktualizovať jeho hodnotu za hodnotu aktuálneho stavu, ak je menšia (našli sme cestu do aktuálneho stavu, ktorá celkovo potrebuje menej kopaní). Pokiaľ sme sa pohli rovnakým smerom, ako vraví aktuálny stav, počet určite voľných políčok (\(Z\)) sa zníži o počet prejdených polí, inak sa o toľko zvýši. Zároveň pre každé dosiahnuté políčko skúsime aktualizovať aj stav s opačným smerom, so zodpovedajúcimi počtami voľných políčok (zvýšenými / zníženými o koľko sme zatiaľ počas pohybu prešli). Keď narazíme na políčko, cez ktoré by sme spadli nižšie, aktualizujeme aj dopadové políčko a skončíme pohyb.

Kopanie je veľmi podobné, skúsime ísť doprava a doľava (rovnako ako pri pohybe), ale budeme aktualizovať políčka o riadok nižšie – ako keby sme prišli k nejakému vzdialenenḿu políčku, vykopali od neho smerom späť k aktuálnemu políčku všetky políčka (vrátane samotného vzdialeného políčka) a potom zoskočili na prvé vykopané políčko, teda sa pohli o jedno doprava alebo doľava.

Ako vyriešime padanie

Hoci sa táto časť môže zdať zložitá (aj keď možno oproti zbytku úlohy ani nie), vieme padanie jednoducho vyriešiť pomocou predpočítania si, kam by sme dopadli, keby sme začali padať z každého políčka.

Pôjdeme od spodku jaskyne po vrch a vždy, keď nájdeme políčko, pod ktorým je kocka, prejdeme postupne všetky voľné políčka nad ním až po prvé políčko s kockou (vrátane, pretože tá by mohla byť v budúcnosti vykopaná), a poznačíme si na ne, o koľko políčok nižšie spadneme, ak sa na nich ocitneme. Môžete si rozmyslieť, že pre každé políčko takto máme len konštantný počet operácií. Dôležité je, že nikdy nenastane situácia, že by sme spadli cez viac než jedno vykopané políčko naraz, keďže sa nevieme hýbať smerom dohora.

Ak potom niekedy zistíme, že by pohyb na voľné políčko alebo pohyb po kopaní spôsobil príliš vysoký pád, jednoducho cieľový stav neaktualizujeme.

Akú to má zložitosť

Pamäťová zložitosť závisí na uložení si jaskyne, výšok pádu (obe zaberajú \(O(V \times S)\) miesta) a najmä samotného stavového priestoru (ten zaberá \(O(V \times S^2)\) miesta, pretože počet vykopaných políčok v každom riadku môže byť až \(O(S)\)). Celková pamäťová zložitosť je teda \(O(V \times S^2)\).

Časová zložitosť závisí na počte stavov (\(O(V \times S^2)\)) a zložitosti prechodov medzi jednotlivými stavmi. V tomto vzoráku sú opísané prechody, ktoré majú zložitosť (pohyb aj kopanie) \(O(S)\), keďže z každého stavu sa pokúšame aktualizovať \(O(S)\) ďalších. Celková časová zložitosť je teda \(O(V \times S^3)\).

Na záver prezradíme, že síce nejde stavový priestor zmenšiť, ale je možné trochu ho zmeniť a vymyslieť zložitejšie prechody, ktoré majú konštantnú zložitosť (čím by sa dala dosiahnuť celková časová zložitosť \(O(V \times S^2)\)). Za odovzdanie takéhoto riešenia v popise bolo možné získať bonusové body.