题目描述

有一个 $H$ 行 $W$ 列的网格，其中恰好有两个格子放置了棋子。

网格的状态由 $H$ 个长度为 W 的字符串 $S_1, \cdots, S_H$ 表示。$S_{i,j} = 'o'$。 表示第 $i$ 行第 $j$ 列的格子上有一个棋子；$S_{i,j} = '-'$。 表示该格子上没有棋子。

现在，小高可以将其中一个棋子移动到相邻的四个格子之一（上、下、左、右），但不能移出网格。请计算将一个棋子移动到另一个棋子所在格子的最少移动次数。

输入格式

输入格式如下：
$H$ $W$
$S_1$
$S_2$
$\vdots$
$S_H$

输出格式

输出一个整数，表示最少移动次数。

样例

2 3
--o
o--

3

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

4

样例1解释

位于第 $1$ 行第 $3$ 列的棋子可以通过 $3$ 步移动到另一个棋子所在的格子：向下、向左、向左。由于不可能用 $2$ 步或更少的步数完成移动，所以答案是 $3$。

数据范围

• $2 ≤ H, W ≤ 100$
• $H$ 和 $W$ 是整数
• $S_i (1 ≤ i ≤ H)$ 是长度为 $W$ 的字符串，仅由 'o' 和 '-' 组成。
• 恰好存在两对整数 $1 ≤ i ≤ H, 1 ≤ j ≤ W$ 满足 $S_{i,j} = 'o'$。

来源

• AtCoder ABC253B