AT_abc253_b [ABC253B] Distance Between Tokens

题目描述

给定一张 $h$ 行 $w$ 列的棋盘。棋盘上有两枚棋子，它们的位置在棋盘中用o表示。棋盘中的空格子用-表示。

一枚棋子可以向它所在格子的上下左右四个相邻的格子中移动（不能出格），称为走一步。请计算其中一枚棋子到达另一枚棋子的位置最少需要多少步。

输入格式

第一行输入两个整数 $h,w$。

接下来输入一个 $h$ 行 $w$ 列，仅由两个o和若干个-组成的字符方阵。

输出格式

一行一个整数，答案。

输入输出样例 #1

输入 #1

2 3
--o
o--

输出 #1

3

输入输出样例 #2

输入 #2

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

输出 #2

4

说明/提示

样例 #1 说明

右上方的棋子走“下、左、左”三步即可到达左下方棋子的位置。

数据规模与约定

对于全部测试点，数据保证：

• $2 \le h,w \le 100$；
• 棋盘中有且仅有两枚棋子。