섬 여행

Farmer John이 소들을 데리고 바다로 휴가를 떠났습니다! 소들은 $R \times C$ 격자($1 \le R, C \le 50$) 위에 놓인 $N$개($1 \le N \le 15$)의 섬에 살고 있습니다. 섬이란 X로 표시된 칸들이 변을 맞대어 연결된 극대 연결 덩어리를 말합니다. 두 X 칸은 변을 공유할 때만 연결되며, 모서리만 맞닿은 두 X 칸은 반드시 연결된 것은 아닙니다.

Bessie는 늦게 도착해 헬리콥터를 타고 오므로, 원하는 섬 아무 곳에나 먼저 내릴 수 있습니다. 그녀는 모든 소를 한 번 이상 만나고 싶어 하므로, $N$개의 섬을 모두 밟을 때까지 섬 사이를 이동합니다.

Farmer John은 연료가 부족해 집에 갈 때까지 다시 날지 않으려 합니다. 다행히 일부 칸은 S로 표시된 얕은 물입니다. Bessie는 얕은 물 칸을 상하좌우 네 방향으로 헤엄쳐 섬 사이를 이동할 수 있습니다. 또한 섬 칸과 인접한 얕은 물 칸 사이를 서로 오갈 수도 있습니다. .로 표시된 깊은 물 칸에는 절대 들어갈 수 없습니다.

모든 섬을 방문하기 위해 Bessie가 헤엄쳐야 하는 최소 거리를 구하세요. 헤엄친 거리는 그녀가 S 칸 위에 서게 되는 서로 다른 횟수입니다. Bessie는 지도를 살펴보고 모든 섬을 방문하는 것이 가능함을 알고 있습니다.

• 첫째 줄: 공백으로 구분된 두 정수 $R$과 $C$.
• 둘째 줄부터 $R+1$번째 줄까지: $i+1$번째 줄에는 격자의 $i$번째 행을 나타내는 $C$개의 문자가 있습니다. 깊은 물은 ., 섬은 X, 얕은 물은 S로 표시됩니다.

• 첫째 줄: 모든 섬을 방문하기 위해 Bessie가 헤엄쳐야 하는 최소 거리를 나타내는 정수 하나.

예시에는 얕은 물길로 연결된 세 개의 섬이 있습니다. Bessie는 왼쪽 위 섬에서 출발해 $1$칸을 헤엄쳐 가운데 섬에 도달하고, 다시 $2$칸을 헤엄쳐 오른쪽 아래 섬에 도달할 수 있으므로 총 $3$칸입니다.