6. Aaaaaaaaa!

V Legolande býva aj Indiana Jones, známy archeológ a akčný hrdina. Všetci s ním radi trávia čas, pretože vedia, že priam priťahuje dobrodružstvo. Nikoho teda neprekvapilo, keď sa jedného dňa Indy pri prechádzke po ulici prepadol cez zatarasený vchod do starodávnej jaskyne.

Indyho to samozrejme veľmi potešilo, najmä preto, že na stene okamžite zbadal mapu jaskyne, ktorá celkom jasne ukazuje, že na samom spodku sa nachádza obrovský poklad. Rád by sa k nemu čo najrýchlejšie dostal (a to, či sa potom dostane aj von, ho momentálne vôbec nezaujíma).

Keďže však jaskyňu našiel náhodou (cestou na nákup), nemá so sebou svoj bič, ani žiadne iné vybavenie, okrem masívneho krompáča (pochopiteľne). Takže keď raz niekam v jaskyni zoskočí, nevie už vyliezť vyššie. Môže niektoré steny jaskyne rozbiť, aby sa dostal ďalej, ale kopať s krompáčom je namáhavé (dokonca viac, než ho nosiť všade so sebou), takže by sa tomu chcel čo najviac vyhnúť.

Pomôžte Indymu naplánovať cestu tak, aby sa dostal na spodok jaskyne a pritom musel čo najmenejkrát použiť krompáč. A ak sa tam dostať nedokáže, povedzte mu, nech tam radšej nelezie.

Úloha

Jaskyňa, ktorú Indy objavil, má tvar mriežky s výškou \(V\) a šírkou \(S\). Niektoré jej políčka sú priechodné, ostatné obsahujú kocky. Kocky síce Indy dokáže rozbiť, ale stojí ho to veľa času. Preto by chcel nájsť takú cestu nadol, ktorú dokáže prejsť s čo najmenším počtom rozbitých kociek. Vôbec mu pritom nevadí, že prejde veľa políčok, keďže chodenie je omnoho menej namáhavé, než rozbíjanie.

Indy začína v ľavom vrchnom rohu jaskyne. Pohybovať sa dokáže len o jedno políčko doprava alebo doľava, ak sa nachádza nad prázdnym políčkom, okamžite spadne. Počas cesty nikdy nesmie spadnúť z väčšej výšky, než \(P\) políčok, inak si ublíži.

Rozbíjať dokáže Indy len kocky, ktoré sa od neho nachádzajú o jeden riadok nižšie, o jedno políčko vedľa a políčka nad nimi sú voľné. V príkladoch nižšie sú všetky takéto kocky označené X, ostatné kocky #, prázdne políčka . a Indyho aktuálna poloha I.

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

Vašou úlohou je vypísať minimálny počet kociek, ktoré musí Indy rozbiť, aby sa dostal na spodok (do ľubovoľného políčka spodného riadku) jaskyne bez toho, aby si ublížil pádom. Ak sa dolu nevie dostať žiadnym spôsobom, vypíšte “Do tejto jaskyne sa liezt neoplati”.

Formát vstupu

V prvom riadku sú čísla \(V\), \(S\) a \(P\) oddelené medzerou. Platí, že \(P \leq V\). Nasleduje \(V\) riadkov dlhých \(S\) znakov – znaky môžu byť . (prázdne políčko) alebo # (kocka). V ľavom hornom políčku tabuľky je vždy prázdne políčko, pod ním je vždy kocka.

Každá zo štyroch testovacích sád je za dva body. V jednotlivých sadách platia nasledovné obmedzenia:

V prvej a tretej sade zároveň platí \(P = V\), teda Indy nikdy nespadne z tak veľkej výšky, aby sa mu niečo stalo.

Formát výstupu

Vypíšte jeden riadok obsahujúci buď číslo (najmenší možný počet kociek, ktoré musí Indy rozbiť, aby sa dostal do spodného riadku jaskyne), alebo reťazec “Do tejto jaskyne sa liezt neoplati”. Nezabudnite vypísať znak konca riadku.

Príklady

Input:

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

Output:

2

Input:

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

Output:

4

Input:

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

Output:

7

Input:

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

Output:

Do tejto jaskyne sa liezt neoplati

V prvom príklade stačí Indymu vykopať kocku na súradniciach [2,1] (súradnice x,y číslujeme od nula od ľavého vrchného rohu), zoskočiť na uvoľnené miesto, spraviť krok doprava, vykopať políčko [2,2] a potom už len dôjsť do cieľa vľavo dole.

V druhom príklade by mohol postupovať podobne a vykopať políčka [3,1], [2,1] a [2,2], ale všimnime si, že potom by spadol z výšky 2, čo by mu ublížilo. Namiesto [2,2] teda musí vykopať [3,2] a potom ešte [3,3].

V treťom príklade môže vykopať [2,1], (potom!) [1,1], ďalej [3,2], [2,2], [4,3], [3,3] a potom buď [4,4] alebo [3,4]. Keby napríklad najskôr nič nekopal a zoskočil rovno na políčko [4,2], nemohol by kopať a zasekol by sa. Všimnite si, že príklady 2 a 3 by sa nemohli vyskytnúť v sadách 1 a 3, pretože nespĺňajú \(P = V\).

Vo štvrtom príklade sa na spodok jaskyne dokopať nevieme. Pre zaujímavosť, dokázať to vieme napríklad tak, že v druhom riadku vieme mať voľné najviac tri políčka, v treťom najviac dve a vo štvrtom najviac jedno, ale žiadne z nich nevie byť na ľavom kraji, preto už sa do piateho riadku nedostaneme.