섬 방문

준석은 친구들과 함께 바다위의 섬으로 휴가를 계획했습니다! 

친구들은 R x C 격자(1 <= R, C <= 50)에 위치한 N 개의 섬(1 <= N <= 15)에서 현재 휴가를 즐기고 있습니다. 섬은 격자에서 'X'로 표시된 사각형을 최대한 연결한 그룹으로, 두 개의 'X'가 한 변을 공유하면 연결됩니다. (따라서, 모서리를 공유하는 두 개의 'X'는 반드시 연결되지 않을 수 있습니다.)

준석은 일정때문에, 헬리콥터를 타고 섬에 늦게 도착합니다. 헬리콥터는 준석이 선택한 섬에 착륙할 수 있습니다. 준석은 자신의 친구들을 적어도 한 번은 보고 싶기 때문에, 모든 N개의 섬을 적어도 한 번은 방문할 때까지 섬과 섬 사이를 이동할 것입니다.

헬리콥터에는 연료가 많이 남아 있지 않으므로, 친구들이 휴가를 마치고 돌아갈 때까지 이를 사용하지 않으려고 합니다. 다행히도, 격자의 일부 칸은 얕은 물있고, 'S'로 표시됩니다. 준석은 이 칸을 통해 네 방향(북, 동, 남, 서)으로 수영하여 섬 사이를 이동할 수 있습니다. 준석은 또한 섬과 얕은 물 사이를 네 방향으로 이동하거나 반대 방향으로 이동할 수 있습니다.

준석이 모든 섬을 방문하기 위해 수영해야 하는 최소 거리를 찾아보세요. (준석이 수영해야 하는 거리는 'S'로 표시된 칸 위에 있는 횟수입니다.)

• 첫 번째 줄 : 두 개의 공백으로 구분된 정수: R과 C.
• 두 번째 줄..R+1 번째 줄 : i+1 번째 줄에는 그리드의 행 i를 나타내는 C개의 문자가 있습니다. 깊은 물 칸은 '.'로 표시되고, 섬 칸은 'X'로 표시되며, 얕은 물 칸은 'S'로 표시됩니다.

• 첫 번째 줄 : 준석이 모든 섬을 방문하기 위해 수영해야 하는 최소 거리를 나타내는 한 개의 정수.