B - Distance Between Tokens 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 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

出力

答えを出力せよ。

入力例 1

2 3
--o
o--

出力例 1

3

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

入力例 2

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

出力例 2

4

Score : 200 points

Problem Statement

There is a grid with H horizontal rows and W vertical columns, in which two distinct squares have a piece.

The state of the squares is represented by H strings S_1, \dots, S_H of length W. S_{i, j} = o means that there is a piece in the square at the i-th row from the top and j-th column from the left; S_{i, j} = - means that the square does not have a piece. Here, S_{i, j} denotes the j-th character of the string S_i.

Consider repeatedly moving one of the pieces to one of the four adjacent squares. It is not allowed to move the piece outside the grid. How many moves are required at minimum for the piece to reach the square with the other piece?

Constraints

  • 2 \leq H, W \leq 100
  • H and W are integers.
  • S_i \, (1 \leq i \leq H) is a string of length W consisting of o and -.
  • There exist exactly two pairs of integers 1 \leq i \leq H, 1 \leq j \leq W such that S_{i, j} = o.

Input

Input is given from Standard Input in the following format:

H W
S_1
\vdots
S_H

Output

Print the answer.

Sample Input 1

2 3
--o
o--

Sample Output 1

3

The piece at the 1-st row from the top and 3-rd column from the left can reach the square with the other piece in 3 moves: down, left, left. Since it is impossible to do so in two or less moves, 3 should be printed.

Sample Input 2

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

Sample Output 2

4