問題文

オシャレ好きのビ太郎は，カーペットを新調した．カーペットは縦 H 行，横 W 列のマス目状に区切られた長方形の形をしており，各マスは白か黒のいずれかの色で塗られている．カーペットの上から i 行目，左から j 列目 (1 \leqq i \leqq H，1 \leqq j \leqq W) にあるマスの色は，文字列 S_{i} の j 文字目が . のとき白色，# のとき黒色である．

ビ太郎は，カーペットの最も左上のマスに駒を置き，以下の操作を何回か行うことで，その駒をカーペットの最も右下のマスに到達させるという遊びを思いついた．

• 駒が置かれているマスと色が異なり，かつ上下左右に隣接するマスを 1 つ選び，そのマスに駒を移動させる．

ビ太郎は，到達までの操作回数をなるべく少なくしたい．ただし，カーペットの模様によっては到達させられないかもしれない．

カーペットの模様の情報が与えられたとき，操作を繰り返すことで左上のマスから右下のマスに駒を到達させることが可能かを判定し，可能ならば操作回数の最小値を求めるプログラムを作成せよ．

制約

• 1 \leqq H \leqq 500．
• 1 \leqq W \leqq 500．
• (H, W) \neq (1, 1)．
• S_{i} は長さ W の文字列である (1 \leqq i \leqq H)．
• S_{i} の 各文字は . または # である (1 \leqq i \leqq H)．
• H, W は整数である．

小課題

1. (4 点) H = 1．
2. (14 点) H \leqq 5，W \leqq 5．
3. (24 点) H \leqq 30，W \leqq 30．
4. (58 点) 追加の制約はない．

採点に関する注意

すべての提出はジャッジシステム上で採点される．

提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解と認められる．

各提出の得点は，提出されたソースコードについて正解と認められた小課題の得点の合計である．

この課題の得点は，この課題に対するすべての提出の得点の最大値である．

現在の得点は「提出結果」タブの「自分の得点状況」から確認できる．

入力例 1

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

出力例 1

9

例えば，図のような操作が考えられる．

左の例では 9 回の操作で，右の例では 13 回の操作で，左上のマスから右下のマスに駒を到達させることが可能である．

9 回よりも少ない操作回数で到達させることは不可能なので，9 を出力する．

この入力例は小課題 2, 3, 4 の制約を満たす．

入力例 2

3 3
...
...
...

出力例 2

-1

はじめから操作ができない場合もある．この場合，駒を右下のマスに到達させることは不可能なので，-1 を出力する．

この入力例は小課題 2, 3, 4 の制約を満たす．

入力例 3

1 5
.#.#.

出力例 3

4

この入力例はすべての小課題の制約を満たす．

入力例 4

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

出力例 4

12

この入力例は小課題 2, 3, 4 の制約を満たす．

入力例 5

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

出力例 5

12

この入力例は小課題 3, 4 の制約を満たす．