102531: [AtCoder]ABC253 B - Distance Between Tokens

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

问题描述

有一个由$H$行和$W$列组成的网格，其中两个不同的正方形各有一个棋子。

正方形的状态由长度为$W$的$H$个字符串$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$的字符串。
• 存在恰好两对整数$1 \leq i \leq H, 1 \leq j \leq W$，使得$S_{i, j} = $ o。

输入

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

$H$ $W$
$S_1$
$\vdots$
$S_H$

输出

输出答案。

样例输入 1

2 3
--o
o--

样例输出 1

3

从顶部数第1行、从左数第3列的棋子可以在3次移动后到达另一个棋子所在的正方形：向下，向左，向左。由于不可能在2次或更少的移动中做到这一点，因此应输出3。

样例输入 2

5 4
-o--
----