Khoảng cách giữa hai điểm

Bối cảnh

Hiếu đang trong nhiệm vụ đi tìm kho báu, trong tay của anh ta có một tấm bản đồ được mô tả theo dạng lưới có \(H\) hàng ngang và \(W\) cột dọc.

Yêu cầu

Trạng thái của các các điểm trên tấm bản đồ bằng \(H\) xâu: \(S_1,..., S_H\) với kích thước là \(W\). Nếu tại điểm \(S_{i, j} =\) o nghĩa là tại đó là kho báu hoặc là điểm Hiếu đang đứng theo mổ tả bản đồ ở tọa độ hàng thứ \(i\) tính từ trên xuống và cột thứ \(j\) tính từ trái sang. Ngược lại nếu \(S_{i, j} =\) - nghĩa là tại đó không có gì cả.

Hiếu chỉ có thể di chuyển lên, xuống, sang trái hoặc sang phải và không được phép di chuyển quân cờ ra ngoài. Trên bản đồ chỉ mô tả kí tự o nhưng anh ta lại không biết chính xác điểm o nào là kho báu và điểm hiện tại anh ta đứng. Anh ta chỉ muốn biết con đường ngắn nhất để đi điểm o đến điểm o còn lại.

Yêu cầu các bạn viết chương trình tính toán thử cần tối thiểu bao nhiêu lần di chuyên để di chuyển giữa hai ô o.

Input

Dòng đầu tiên chứa hai số nguyên \(H\) và \(W\) \((2 \le H, W \le 100)\).

\(H\) dòng tiếp theo, mỗi dòng chứa một xâu với kích thước là \(W\), chỉ bao gồm 1 trong 2 kí tự là - hoặc o.

Output

In ra số nguyên duy nhất, là số bước tối thiểu để di chuyển giữa hai ô có kí tự o.

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

2 3
--o
o--

Output

3

Giải thích ví dụ

Ví dụ

Ví dụ 2

Input

2 3
--o
o--

Giải thích ví dụ

• Để di chuyển giữa hai điểm o, bạn cần di chuyển từ (0,2) đến (1,0) với số bước tối thiểu là 3 (di chuyển xuống, trái, trái).

Thông tin học tập

• Buổi: B11
• Concepts: 2D arrays, row/column/diagonal traversal
• Giới hạn kiến thức: B01-B11
• Time limit: 1 second
• Memory limit: 128 MB
• Point: 20