Problem T
Mink
Ministeriet har udlovet en dusør på $d$ kr. per minkkadaver. Idet Langgården indeholder en række store minkgravpladser, virker det som en udmærket indtægtskilde. På den anden side er der omkostninger forbundet med udgravningsarbejdet.
Langgårdens systemer for sensorbaserede jordbundsanalyser til lokalisering af underjordisk forrådnelse er efterhånden så sofistikerede, at Rued og Valborg hurtigt kan fremtage nøjagtige kort over positionen af hver nedgravede mink på området. Dermed bliver det muligt at identificere de mink, det kan betale sig at grave op.
En minkgrav består af jord og minkkadavere. Det koster $1$ kr. at grave en enhed jord op. Vi betragter minkgraven som et lodret tværsnit tegnet som et gitter af højde $h$ og bredde $b$, hver position er angivet som et rækkenummer $r\in \{ 0,\ldots , h-1\} $ og et søjlenummer $s\in \{ 0,\ldots ,b-1\} $. Øverste lag er række $0$. Der kan kun »graves nedad«, dvs. at for at fjerne en enhed jord på position $(r, s)$ for $r>0$, så skal position $(r-1, s)$ ligeledes være ryddet. En mink er tre enheder lang og kan kun »løftes opad«; dvs. at for at kunne fjerne en mink på positioner $(r,s)$, $(r,s+1)$ og $(r,s+2)$, så skal $(r-1,s)$, $(r-1,s+1)$ og $(r-1,s+2)$ være ryddet.
Betragt for eksempel følgende minkgrav med tre nedgravede mink:
![\includegraphics[width=.3\textwidth ]{img/sample1.pdf}](/problems/itu.mink/file/statement/da/img-0002.png)
Hver af de følgende tre udgravninger er gyldige, uden dog nødvendigvis at være optimale:
![\includegraphics[width=.9\textwidth ]{img/sample1-ok.pdf}](/problems/itu.mink/file/statement/da/img-0003.png)
Derimod er de følgende tre udgravninger ugyldige og ville blive bedømt som forkert svar.
![\includegraphics[width=.9\textwidth ]{img/sample1-wa.pdf}](/problems/itu.mink/file/statement/da/img-0004.png)
Indlæsning
På første linje, tre positive heltal $h$, $b$ og $d$. Der gælder $3\leq h\leq 200$, $5\leq b\leq 200$ og $4\leq d\leq 600$.
Herefter følger et kort over minkgraven af højde $h$ og bredde $b$. Her beskriver # en enhed jord, og <=> beskriver en mink. Der er mindst $1$ og højst $200$ mink.
Minkene er gravet forsvarligt ned for ikke at få bøvl med sundhedsmyndighederne, så første linje (svarende til øverste række) består udelukkende af jord. Desuden kan du gå ud fra, at første og sidste tegn i hver linje samt hele sidste linje ligeledes er jord.
Udskrift
Præcis $h$ linjer af længde $b$, som beskriver minkgraven efter udgravning. De udgravede positioner er angivet med mellemrum; alle andre positioner skal være identiske med indlæsningen.
Pointsætning
Dit program bliver brugt på $10$ forskellige testfald. Hvert af disse testfald kan give mellem $0$ og $10$ point. Nærmere betegnet gives $\lceil 10\cdot p/ q\rceil $ point for et testfald, når din løsning er gyldigt og opnår ikke-negativ profit $p$ kr., og en optimal løsning giver $q$ kr. Dit svar bliver bedømt som forkert svar og giver $0$ point, hvis din udgravning er ugyldig eller har negativ profit. Totalt kan der opnås $100$ point.
Svarene på eksempelinstanserne forneden er alle optimale.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 20 7 #################### #############<=>#### ####<=>############# ###########<=>###### #################### |
#### ###### #### #### ###### #### #### ############# ###########<=>###### #################### |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 20 6 #################### #############<=>#### ####<=>############# ###########<=>###### #################### |
############# #### ############# #### ####<=>############# ###########<=>###### #################### |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 5 4 ##### #<=># #<=># ##### ##### ##### #<=># #<=># #<=># ##### |
# # # # # # # # # # # # # # # # # # ##### |
| Sample Input 4 | Sample Output 4 |
|---|---|
4 8 4 ######## #<=>#### #<=><=># ######## |
# #### # #### # <=># ######## |
| Sample Input 5 | Sample Output 5 |
|---|---|
3 5 4 ##### #<=># ##### |
# # # # ##### |
