← 返回比赛

已结束 GESP挑战赛#13

← 上一题下一题 →

A4694 | $CityWalk$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

时间限制:1000ms 空间限制:128mb 利尔萨维敏萨是一所海上都市，他的地图结构可以被视为是一副大小为$h \times w$ 的矩阵。 两名旅行家来到了这座城市，他们想要一起逛逛。首先他们需要碰到一起才可以。 在矩阵当中只会存在两种字符，分别为-与o，分别代表道路与两位旅行家当前的所在地。旅行家每一秒都可以向着当前所在位置$x,y$的上下左右任意一个方向行走一格，请问他们总共最少需要几步才可以碰面？ 注: 他们不可以走到这个矩阵外～

输入格式

第一行输入两个整数$h,w$，代表矩阵大小。 随后$h$行，每行输入一个长度为$w$的字符串$S_i$，代表矩阵。

输出格式

输出一个整数,表示最少步数

输入输出样例

输入 #1

3 4
o---
----
--o-

输出 #1

C++ 编辑器

输入

输出