有一个H行和W列的网格，一共有H*W个方块，其中在两个不同的方块中各有一个令牌。
正方形的状态由H行字符串Si表示
每个字符串长度W
第i行的第j个字符表示为S[i][j]
S[i][j]=o表示在从顶部开始的第i行和从左侧开始的第j列的正方形中有一个令牌；
S[i][j]=-表示正方形没有块。
注意这里，S[i][j]
表示字符串Si的第j个字符，也就是这个网格中第i行第j列上的字符。
考虑重复将其中一令牌移动到四个相邻方块中的一个，不允许将其移出网格范围之外。要使其中一个令牌与另一个令牌重叠，至少需要多少次移动？
约束条件
2 ≤H、 W≤100
H和W是整数。
Si (1≤i≤H） 是长度为W的字符串，由o和-。
正好存在两对整数1≤i≤H、 1个≤j≤W这样Si、 j=o。
Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 200200 points
Problem Statement
There is a grid with HH horizontal rows and WW vertical columns, in which two distinct squares have a piece.
The state of the squares is represented by HH strings S_1, \dots, S_HS1,…,SH of length WW. S_{i, j} =Si,j= o means that there is a piece in the square at the ii-th row from the top and jj-th column from the left; S_{i, j} =Si,j= - means that the square does not have a piece. Here, S_{i, j}Si,j denotes the jj-th character of the string S_iSi.
Consider repeatedly moving one of the pieces to one of the four adjacent squares. It is not allowed to move the piece outside the grid. How many moves are required at minimum for the piece to reach the square with the other piece?
Constraints
-
2 \leq H, W \leq 1002≤H,W≤100
-
HH and WW are integers.
-
S_i \, (1 \leq i \leq H)Si(1≤i≤H) is a string of length WW consisting of o and -.
-
There exist exactly two pairs of integers 1 \leq i \leq H, 1 \leq j \leq W1≤i≤H,1≤j≤W such that S_{i, j} =Si,j= o.
Input
Input is given from Standard Input in the following format:
HHWWS_1S1\vdots⋮S_HSH
Output
Print the answer.