两个棋子的距离

题目描述

有一个 $H$ 行 $W$ 列的网格，其中两个互不相同的格子中各放着一个棋子。

网格的状态用 $H$ 个长度为 $W$ 的字符串 $S_1, \dots, S_H$ 表示。$S_{i, j} =$ o 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子中有棋子；$S_{i, j} =$ - 表示该格子中没有棋子。这里 $S_{i, j}$ 表示字符串 $S_i$ 的第 $j$ 个字符。

现在考虑反复将某个棋子移动到相邻的四个格子之一。不允许将棋子移出网格。请问棋子移动到另一个棋子所在格子至少需要多少次移动？

输入格式

输入按以下格式从标准输入给出：

H W
S_1
⋮
S_H

输出格式

打印答案。

样例

2 3
--o
o--

3

位于从上往下第 1 行、从左往右第 3 列的棋子可以按「下、左、左」3 步移动到另一个棋子所在的格子。由于无法在两步或更少步内到达，因此应输出 3。

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

4

数据范围

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