4167： Distance Between Tokens

# Distance Between Tokens ### 内存 1024MB ### 时间 2S ## 题目描述 配套书籍购买链接：https://item.jd.com/10127270863925.html 有一个 $H$ 行 $W$ 列的网格，其中恰好有两个格子放置了棋子。 网格的状态由 $H$ 个长度为 W 的字符串 $S_1, \cdots, S_H$ 表示。$S_{i,j} = 'o'$。 表示第 $i$ 行第 $j$ 列的格子上有一个棋子；$S_{i,j} = '-'$。 表示该格子上没有棋子。 现在，小高可以将其中一个棋子移动到相邻的四个格子之一（上、下、左、右），但不能移出网格。请计算将一个棋子移动到另一个棋子所在格子的最少移动次数。 ## 输入格式 输入格式如下： $H$ $W$ $S_1$ $S_2$ $\vdots$ $S_H$ ## 输出格式 输出一个整数，表示最少移动次数。 ## 输入输出样例 ### 输入样例1 ``` 2 3 --o o-- ``` ### 输出样例1 ``` 3 ``` ### 输入样例2 ``` 5 4 -o-- ---- ---- ---- -o-- ``` ### 输出样例2 ``` 4 ``` ## 数据范围与提示 【样例$1$说明】 位于第 $1$ 行第 $3$ 列的棋子可以通过 $3$ 步移动到另一个棋子所在的格子：向下、向左、向左。由于不可能用 $2$ 步或更少的步数完成移动，所以答案是 $3$。 【数据范围】 - $2 ≤ H, W ≤ 100$ - $H$ 和 $W$ 是整数 - $S_i (1 ≤ i ≤ H)$ 是长度为 $W$ 的字符串，仅由 '`o`' 和 '`-`' 组成。 - 恰好存在两对整数 $1 ≤ i ≤ H, 1 ≤ j ≤ W$ 满足 $S_{i,j} = 'o'$。 ## 题目来源 ABC253B