カーペット (Carpet)

オシャレ好きのビ太郎は，カーペットを新調した．カーペットは縦 \(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\) 点) 追加の制約はない．

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

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

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

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

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

JOI 2022 · JCIOI · CC BY-SA 4.0

入力は以下の形式で標準入力から与えられる．

\(H\) \(W\)
\(S_{1}\)
\(S_{2}\)
\(\vdots\)
\(S_{H}\)

操作を繰り返すことで左上のマスから右下のマスに駒を到達させることが可能な場合は操作回数の最小値を，不可能な場合は -1 を，標準出力に \(1\) 行で出力せよ．