分数: 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