题目描述

有一个字符网格 $S$，包含 $H$ 行和 $W$ 列，其中有两个不同的方格上放着棋子。

其中，$S_{i,j} =$ o 表示在第 $i$ 行、第 $j$ 列的方格上有一个棋子；$S_{i,j} =$ - 表示该方格上没有棋子。

考虑反复将其中一个棋子移动到相邻的四个方格中的一个。移动时不能将棋子移出网格。问至少需要多少步，棋子才能到达另一个棋子所在的方格？

输入格式

第一行输入两个整数分别为 $H,W$

接下来 $H$ 行，每行输入 $W$ 个字符。

输出格式

输出答案

2 3
--o
o--

3

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

4

提示

数据范围

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

样例 1 解释

位于从上数第 $1$ 行、第 $3$ 列的棋子可以通过 $3$ 步到达另一个棋子所在的方格：下、左、左。由于不可能在两步或更少的步数内到达，因此应输出 $3$。