Tehtävänanto

Tyylikäs Bitaro on hankkinut uuden maton. Matto on suorakulmion muotoinen ja jaettu ruudukkoon, jossa on pystysuunnassa $H$ riviä ja vaakasuunnassa $W$ saraketta, ja jokainen ruutu on väriltään joko valkoinen tai musta. Maton ylhäältä lukien $i$-nnen rivin ja vasemmalta lukien $j$-nnen sarakkeen ($1 \le i \le H$, $1 \le j \le W$) ruudun väri on valkoinen, kun merkkijonon $S_i$ $j$-s merkki on ., ja musta, kun se on #.

Bitaro keksi leikin, jossa hän asettaa pelinappulan maton vasemmanpuoleisimpaan yläruutuun ja yrittää saada nappulan maton oikeanpuoleisimpaan alaruutuun suorittamalla seuraavan operaation jonkin määrän kertoja:

• Valitse $1$ ruutu, joka on eri värinen kuin ruutu, jossa nappula tällä hetkellä on, ja joka on sen vieressä ylä-, ala-, vasemmalla tai oikealla puolella, ja siirrä nappula tähän ruutuun.

Bitaro haluaa päästä perille mahdollisimman vähillä operaatioilla. Maton kuviosta riippuen perille pääseminen ei kuitenkaan välttämättä ole mahdollista.

Kun maton kuvion tiedot annetaan, kirjoita ohjelma, joka selvittää, onko nappula mahdollista saada vasemmasta yläruudusta oikeaan alaruutuun toistamalla operaatiota, ja jos on, määrittää pienimmän mahdollisen operaatioiden määrän.

Rajoitukset

• $1 \le H \le 500$.
• $1 \le W \le 500$.
• $(H, W) \neq (1, 1)$.
• $S_i$ on pituudeltaan $W$ oleva merkkijono ($1 \le i \le H$).
• Jokainen merkkijonon $S_i$ merkki on . tai # ($1 \le i \le H$).
• $H, W$ ovat kokonaislukuja.

Osatehtävät

1. ($4$ pistettä) $H = 1$.
2. ($14$ pistettä) $H \le 5$, $W \le 5$.
3. ($24$ pistettä) $H \le 30$, $W \le 30$.
4. ($58$ pistettä) Ei lisärajoituksia.

Syöte

Syöte annetaan vakiosyötteestä seuraavassa muodossa:

H W
S_1
S_2
:
S_H

Tuloste

Jos nappula on mahdollista saada vasemmasta yläruudusta oikeaan alaruutuun toistamalla operaatiota, tulosta pienin mahdollinen operaatioiden määrä; jos se on mahdotonta, tulosta -1 vakiotulosteeseen $1$ riville.

Esimerkit

Esimerkkisyöte 1

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

Esimerkkituloste 1

9

Esimerkiksi kuvan mukaiset operaatiot ovat mahdollisia.

Vasemmanpuoleisessa esimerkissä nappula saadaan vasemmasta yläruudusta oikeaan alaruutuun $9$ operaatiolla ja oikeanpuoleisessa esimerkissä $13$ operaatiolla.

Koska perille ei ole mahdollista päästä vähemmällä kuin $9$ operaatiolla, tulostetaan $9$.

Tämä esimerkkisyöte täyttää osatehtävien $2, 3, 4$ rajoitukset.

Esimerkkisyöte 2

3 3
...
...
...

Esimerkkituloste 2

-1

On myös tapauksia, joissa operaatioita ei voida suorittaa lainkaan alusta alkaen. Tällöin nappulaa ei voida saada oikeaan alaruutuun, joten tulostetaan -1.

Tämä esimerkkisyöte täyttää osatehtävien $2, 3, 4$ rajoitukset.

Esimerkkisyöte 3

1 5
.#.#.

Esimerkkituloste 3

4

Tämä esimerkkisyöte täyttää kaikkien osatehtävien rajoitukset.

Esimerkkisyöte 4

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

Esimerkkituloste 4

12

Tämä esimerkkisyöte täyttää osatehtävien $2, 3, 4$ rajoitukset.

Esimerkkisyöte 5

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

Esimerkkituloste 5

12

Tämä esimerkkisyöte täyttää osatehtävien $3, 4$ rajoitukset.