/ 
実行時間制限: 2 sec / メモリ制限: 256 MB
配点：400 点
問題文
縦 H マス, 横 W マスに広がるマス目があり, 各マスは白または黒で塗られている. 上から i 番目で左から j 番目のマスを (i, j) で表す.
すぬけ君は, このマス目を使って次のようなゲームをしたい. ゲームの開始時点ではマス (1, 1) にゲームキャラクター「けぬす君」がいる. プレイヤーはけぬす君を上下左右の 4 方向のいずれかに 1 マスだけ動かすことを繰り返す. けぬす君が白いマスだけを通って (H, W) にたどり着けばゲームクリアとなる.
ゲームを開始する前に, すぬけ君はいくつかの白いマス目の色を黒に変えることができる. ただし, マス (1, 1) と (H, W) の色を変えることはできず, ゲームを開始するまでにすべての色の変更を行わなければならない.
ゲームをクリアしたとき, ゲームの開始前にマスの色を変えた回数がすぬけ君のスコアとなる. そのとき, すぬけ君が取る可能性のある最大のスコアを求めなさい.ただし, すぬけ君がどのようにマス目の色を変えてもけぬす君が (H, W) にたどり着くことが出来ない場合、-1 と出力しなさい.
ただし, 各マスの色の情報は文字 s_{i, j} として与えられる. マス (i, j) が最初白で塗られている場合 s_{i, j} は . であり, マス (i, j) が最初黒で塗られている場合 s_{i, j} は # である.
制約
- H は 2 以上 50 以下の整数
- W は 2 以上 50 以下の整数
- s_{i, j} は
.または#(1 \leq i \leq H, 1 \leq j \leq W) - s_{1, 1}, s_{H, W} は
.である
入力
入力は以下の形式で標準入力から与えられる.
H W
s_{1, 1}s_{1, 2}s_{1, 3} ... s_{1, W}
s_{2, 1}s_{2, 2}s_{2, 3} ... s_{2, W}
: :
s_{H, 1}s_{H, 2}s_{H, 3} ... s_{H, W}
出力
すぬけ君が取る可能性のある最大のスコアを出力しなさい. ただし, すぬけ君がどのようにマス目の色を変えてもけぬす君が (H, W) にたどり着くことが出来ない場合、-1 と出力しなさい.
入力例 1
3 3 ..# #.. ...
出力例 1
2
下の図のようにマス目の色を変えれば, スコア 2 を達成できます.
入力例 2
10 37 ..................................... ...#...####...####..###...###...###.. ..#.#..#...#.##....#...#.#...#.#...#. ..#.#..#...#.#.....#...#.#...#.#...#. .#...#.#..##.#.....#...#.#.###.#.###. .#####.####..#.....#...#..##....##... .#...#.#...#.#.....#...#.#...#.#...#. .#...#.#...#.##....#...#.#...#.#...#. .#...#.####...####..###...###...###.. .....................................
出力例 2
209
Score: 400 points
Problem statement
We have an H \times W grid whose squares are painted black or white. The square at the i-th row from the top and the j-th column from the left is denoted as (i, j).
Snuke would like to play the following game on this grid. At the beginning of the game, there is a character called Kenus at square (1, 1). The player repeatedly moves Kenus up, down, left or right by one square. The game is completed when Kenus reaches square (H, W) passing only white squares.
Before Snuke starts the game, he can change the color of some of the white squares to black. However, he cannot change the color of square (1, 1) and (H, W). Also, changes of color must all be carried out before the beginning of the game.
When the game is completed, Snuke's score will be the number of times he changed the color of a square before the beginning of the game. Find the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed, that is, Kenus can never reach square (H, W) regardless of how Snuke changes the color of the squares.
The color of the squares are given to you as characters s_{i, j}. If square (i, j) is initially painted by white, s_{i, j} is .; if square (i, j) is initially painted by black, s_{i, j} is #.
Constraints
- H is an integer between 2 and 50 (inclusive).
- W is an integer between 2 and 50 (inclusive).
- s_{i, j} is
.or#(1 \leq i \leq H, 1 \leq j \leq W). - s_{1, 1} and s_{H, W} are
..
Input
Input is given from Standard Input in the following format:
H W
s_{1, 1}s_{1, 2}s_{1, 3} ... s_{1, W}
s_{2, 1}s_{2, 2}s_{2, 3} ... s_{2, W}
: :
s_{H, 1}s_{H, 2}s_{H, 3} ... s_{H, W}
Output
Print the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed.
Sample Input 1
3 3 ..# #.. ...
Sample Output 1
2
The score 2 can be achieved by changing the color of squares as follows:
Sample Input 2
10 37 ..................................... ...#...####...####..###...###...###.. ..#.#..#...#.##....#...#.#...#.#...#. ..#.#..#...#.#.....#...#.#...#.#...#. .#...#.#..##.#.....#...#.#.###.#.###. .#####.####..#.....#...#..##....##... .#...#.#...#.#.....#...#.#...#.#...#. .#...#.#...#.##....#...#.#...#.#...#. .#...#.####...####..###...###...###.. .....................................
Sample Output 2
209