Lýsing á verkefni

Bitaro, sem hefur gaman af tísku, keypti sér nýtt teppi. Teppið er rétthyrnt og skiptist í grind með $H$ röðum lóðrétt og $W$ dálkum lárétt, og hver reitur er málaður annaðhvort hvítur eða svartur. Litur reitsins í $i$-tu röð að ofan og $j$-ta dálki frá vinstri ($1 \le i \le H$, $1 \le j \le W$) á teppinu er hvítur þegar $j$-ta táknið í strengnum $S_i$ er ., en svartur þegar það er #.

Bitaro datt í hug leikur þar sem hann setur leikmann á reitinn efst til vinstri á teppinu og kemur honum á reitinn neðst til hægri á teppinu með því að framkvæma eftirfarandi aðgerð nokkrum sinnum:

• Veldu $1$ reit sem hefur annan lit en reiturinn sem leikmaðurinn er á núna og liggur að honum að ofan, neðan, vinstri eða hægri, og færðu leikmanninn á þann reit.

Bitaro vill að fjöldi aðgerða til að komast á leiðarenda sé sem minnstur. Hins vegar gæti verið ómögulegt að komast þangað, allt eftir mynstri teppisins.

Gefnar upplýsingar um mynstur teppisins, skrifið forrit sem ákvarðar hvort hægt sé að koma leikmanninum frá reitnum efst til vinstri á reitinn neðst til hægri með því að endurtaka aðgerðina, og ef það er hægt, finnur lágmarksfjölda aðgerða.

Takmarkanir

• $1 \le H \le 500$.
• $1 \le W \le 500$.
• $(H, W) \neq (1, 1)$.
• $S_i$ er strengur af lengd $W$ ($1 \le i \le H$).
• Hvert tákn í $S_i$ er . eða # ($1 \le i \le H$).
• $H, W$ eru heiltölur.

Undirverkefni

1. ($4$ stig) $H = 1$.
2. ($14$ stig) $H \le 5$, $W \le 5$.
3. ($24$ stig) $H \le 30$, $W \le 30$.
4. ($58$ stig) Engar viðbótartakmarkanir.

Inntak

Inntakið er gefið úr staðalinntaki á eftirfarandi sniði:

H W
S_1
S_2
:
S_H

Úttak

Ef hægt er að koma leikmanninum frá reitnum efst til vinstri á reitinn neðst til hægri með því að endurtaka aðgerðina skal skrifa út lágmarksfjölda aðgerða; ef það er ómögulegt skal skrifa út -1 í $1$ línu á staðalúttak.

Dæmi

Sýnidæmi um inntak 1

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

Sýnidæmi um úttak 1

9

Til dæmis má hugsa sér aðgerðirnar sem sýndar eru á myndinni.

Í dæminu til vinstri er hægt að koma leikmanninum frá reitnum efst til vinstri á reitinn neðst til hægri í $9$ aðgerðum, og í dæminu til hægri í $13$ aðgerðum.

Þar sem ómögulegt er að komast þangað í færri en $9$ aðgerðum er $9$ skrifað út.

Þetta sýnidæmi uppfyllir takmarkanir undirverkefna $2, 3, 4$.

Sýnidæmi um inntak 2

3 3
...
...
...

Sýnidæmi um úttak 2

-1

Það kemur fyrir að ekki er hægt að framkvæma neina aðgerð strax í upphafi. Í þessu tilviki er ómögulegt að koma leikmanninum á reitinn neðst til hægri, svo skrifað er út -1.

Þetta sýnidæmi uppfyllir takmarkanir undirverkefna $2, 3, 4$.

Sýnidæmi um inntak 3

1 5
.#.#.

Sýnidæmi um úttak 3

4

Þetta sýnidæmi uppfyllir takmarkanir allra undirverkefna.

Sýnidæmi um inntak 4

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

Sýnidæmi um úttak 4

12

Þetta sýnidæmi uppfyllir takmarkanir undirverkefna $2, 3, 4$.

Sýnidæmi um inntak 5

7 5
.#.##
##...
.#.##
.###.
##.#.
...#.
##.#.

Sýnidæmi um úttak 5

12

Þetta sýnidæmi uppfyllir takmarkanir undirverkefna $3, 4$.