Énoncé du problème

Bitaro, qui aime la mode, a acheté un nouveau tapis. Le tapis a une forme rectangulaire divisée en une grille de $H$ lignes verticalement et $W$ colonnes horizontalement, et chaque case est peinte soit en blanc, soit en noir. La couleur de la case située à la $i$-ème ligne depuis le haut et à la $j$-ème colonne depuis la gauche ($1 \le i \le H$, $1 \le j \le W$) du tapis est blanche lorsque le $j$-ème caractère de la chaîne $S_i$ est ., et noire lorsqu'il est #.

Bitaro a imaginé un jeu consistant à placer un pion sur la case située le plus en haut à gauche du tapis et à le faire atteindre la case située le plus en bas à droite du tapis en effectuant plusieurs fois l'opération suivante :

• Choisir $1$ case d'une couleur différente de celle où se trouve actuellement le pion et qui lui est adjacente verticalement ou horizontalement, puis déplacer le pion sur cette case.

Bitaro souhaite réduire au minimum le nombre d'opérations nécessaires pour atteindre l'arrivée. Cependant, selon le motif du tapis, il se peut qu'il soit impossible d'y parvenir.

Étant donné les informations sur le motif du tapis, écrivez un programme permettant de déterminer s'il est possible de faire atteindre au pion la case en bas à droite depuis la case en haut à gauche en répétant l'opération, et si oui, de trouver le nombre minimal d'opérations.

Contraintes

• $1 \le H \le 500$.
• $1 \le W \le 500$.
• $(H, W) \neq (1, 1)$.
• $S_i$ est une chaîne de caractères de longueur $W$ ($1 \le i \le H$).
• Chaque caractère de $S_i$ est . ou # ($1 \le i \le H$).
• $H, W$ sont des entiers.

Sous-tâches

1. ($4$ points) $H = 1$.
2. ($14$ points) $H \le 5$, $W \le 5$.
3. ($24$ points) $H \le 30$, $W \le 30$.
4. ($58$ points) Aucune contrainte supplémentaire.

Entrée

L'entrée est fournie depuis l'entrée standard sous le format suivant :

H W
S_1
S_2
:
S_H

Sortie

S'il est possible de faire atteindre au pion la case en bas à droite depuis la case en haut à gauche en répétant l'opération, affichez le nombre minimal d'opérations ; si c'est impossible, affichez -1, sur $1$ ligne sur la sortie standard.

Exemples d'entrée/sortie

Exemple d'entrée 1

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

Exemple de sortie 1

9

Par exemple, on peut envisager les opérations illustrées sur la figure.

Dans l'exemple de gauche, il est possible de faire atteindre au pion la case en bas à droite depuis la case en haut à gauche en $9$ opérations, et dans l'exemple de droite en $13$ opérations.

Comme il est impossible d'y parvenir en moins de $9$ opérations, on affiche $9$.

Cet exemple d'entrée satisfait les contraintes des sous-tâches $2, 3, 4$.

Exemple d'entrée 2

3 3
...
...
...

Exemple de sortie 2

-1

Il arrive qu'aucune opération ne soit possible dès le départ. Dans ce cas, comme il est impossible de faire atteindre au pion la case en bas à droite, on affiche -1.

Cet exemple d'entrée satisfait les contraintes des sous-tâches $2, 3, 4$.

Exemple d'entrée 3

1 5
.#.#.

Exemple de sortie 3

4

Cet exemple d'entrée satisfait les contraintes de toutes les sous-tâches.

Exemple d'entrée 4

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

Exemple de sortie 4

12

Cet exemple d'entrée satisfait les contraintes des sous-tâches $2, 3, 4$.

Exemple d'entrée 5

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

Exemple de sortie 5

12

Cet exemple d'entrée satisfait les contraintes des sous-tâches $3, 4$.