配点 : $200$ 点

問題文

$H$ 行 $W$ 列のマス目があり、そのうち二つの異なるマスに駒が置かれています。

マス目の状態は $H$ 個の長さ $W$ の文字列 $S_1, \dots, S_H$ で表されます。$S_{i, j} =$ o ならば $i$ 行目 $j$ 列目のマスに駒が置かれていることを、$S_{i, j} =$ - ならばそのマスには駒が置かれていないことを表します。なお、$S_{i, j}$ は文字列 $S_i$ の $j$ 文字目を指します。

一方の駒をマス目の外側に出ないように上下左右の隣接するマスに動かすことを繰り返すとき、もう一方の駒と同じマスに移動させるためには最小で何回動かす必要がありますか？

制約

• $2 \leq H, W \leq 100$
• $H, W$ は整数
• $S_i \, (1 \leq i \leq H)$ は o および - のみからなる長さ $W$ の文字列
• $S_{i, j} =$ o となる整数 $1 \leq i \leq H, 1 \leq j \leq W$ の組がちょうど二つ存在する

入力

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

$H$ $W$

$S_1$

$\vdots$

$S_H$

出力

答えを出力せよ。

2 3
--o
o--

3

$1$ 行目 $3$ 列目に置かれている駒を 下 $\rightarrow$ 左 $\rightarrow$ 左 と移動すると $3$ 回でもう一方の駒と同じマスに移動させることができます。$2$ 回以下で移動させることはできないので、$3$ を出力します。

5 4
-o--
----
----
----
-o--

4