Distance Between Tokens

题目描述

有一个由 $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$ $\vdots$ $S_H$

输出格式

输出答案。

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$ 的字符串。 存在恰好两个整数对 $1 \leq i \leq H, 1 \leq j \leq W$ 满足 $S_{i, j} =$ $o$。位于从上数第 $1$ 行第 $3$ 列的棋子可以通过 $3$ 步到达另一枚棋子所在的格子：向下、向左、向左。由于不可能在两步或更少的移动中做到，所以应当输出 $3$。

标签: AtCoder|abc253B

来源

AtCoder|abc253B