Score : $200$ points

问题描述

存在一个具有 $H$ 行（水平方向）和 $W$ 列（垂直方向）的网格，在其中两个不同的格子内各有一个棋子。

格子的状态通过长度为 $W$ 的 $H$ 个字符串 $S_1, \dots, S_H$ 来表示。若 $S_{i, j} =$ o，则表示在从上到下第 $i$ 行、从左到右第 $j$ 列的格子中存在一个棋子；若 $S_{i, j} =$ -，则表示该格子中没有棋子。这里，$S_{i, j}$ 表示字符串 $S_i$ 中的第 $j$ 个字符。

考虑反复将一个棋子移动到其四个相邻的格子之一。不允许将棋子移出网格范围。请问至少需要多少步才能使一个棋子到达另一个棋子所在的格子？

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 10:47:19