← 返回题目列表

AtCoder · abc253_b

D. 令牌之间的距离

中文机器翻译题面 查看原题

分数: 200 点

问题陈述

有一个网格 H 水平行和 W 垂直列,其中两个不同的方块各有一块。

方块的状态由下式表示 H 字符串 S_1, \dots, S_H 长度 W. S_{i, j} = o 表示在该方格内有一个棋子 i从顶部开始的第行和 j左起第 列; S_{i, j} = - 表示该正方形没有棋子。 在这里, S_{i, j} 表示 j- 字符串的第一个字符 S_i.

考虑重复将其中一个棋子移动到四个相邻方格之一。 不允许将棋子移出网格。 至少需要移动多少步才能使棋子到达与另一棋子相交的格子?

约束

  • 2 \leq H, W \leq 100
  • H 和 W 是整数。
  • S_i \, (1 \leq i \leq H) 是一个长度为 W 组成 o 和 -.
  • 恰好存在两对整数 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- 从顶部开始的第 1 行 3- 从左边算起的第 1 列可以到达另一块在的正方形 3 移动:下、左、左。 由于不可能在两步或更少的时间内完成, 应打印 3 。


示例输入 2

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

示例输出 2

4