델프트 거리

당신은 델프트 북서쪽 모서리에 있는 호텔에 머물고 있으며, 남동쪽 모서리에 있는 대학의 대회장으로 가려고 합니다. 그 경로는 도시의 역사 지구를 바로 지나갑니다. 맨해튼과 마찬가지로 도시는 $h \times w$ 격자 형태의 건물로 이루어져 있습니다. 다만 맨해튼과 달리 격자 안에는 둥근 중세 탑도 있습니다. 정사각형 건물은 모두 축에 평행하며 한 변의 길이가 $10 \text{m}$입니다. 둥근 탑은 모두 지름이 $10 \text{m}$입니다. 이웃한 두 건물 사이에는 폭을 무시할 수 있는 좁은 골목이 하나 나 있을 만큼의 공간이 있습니다. 대회는 이미 시작되었고 당신은 늦었으므로, 호텔에서 대회장까지 가장 짧은 경로를 찾아야 합니다. 다행히 도시 지도가 있습니다. 그림 D.1을 참고하세요.

그림 D.1: 첫 번째 입력에 해당하는 도시 지도이며, 빨간색으로 최단 경로를 표시하였습니다.

첫 줄에 두 정수 $h$와 $w$ ($1 \leq h,w \leq 700$)가 주어집니다. 이는 지도에 표시된 건물의 행 수와 열 수입니다. 이어서 $h$개의 줄에 각각 $w$개의 문자가 주어집니다. 각 문자는 둥근 탑을 뜻하는 'O' 또는 정사각형 건물을 뜻하는 'X'입니다. 지도는 북쪽이 위를 향합니다.

델프트의 북서쪽 모서리에서 남동쪽 모서리까지 가장 짧은 경로의 길이를 미터 단위로 출력합니다. 상대 오차 또는 절대 오차가 $10^{-6}$ 이하이면 정답으로 인정합니다.