레이팅 미적용농부 존이 소들을 데리고 바다로 휴가를 떠났다! 소들은 R x C 격자 (1 <= R, C <= 50) 위에 있는 N (1 <= N <= 15)개의 섬에 살고 있다. 섬은 격자에서 'X'로 표시된 칸들의 극대 연결 그룹으로, 두 'X'는 변을 공유하면 연결된 것이다. (따라서 꼭짓점만 공유하는 두 'X'는 반드시 연결된 것은 아니다.)
그런데 베시는 늦게 도착해서 농부 존과 함께 헬리콥터를 타고 온다. 따라서 그녀는 원하는 아무 섬에나 처음 착륙할 수 있다. 그녀는 모든 소를 적어도 한 번씩 방문하고 싶으므로, N개의 섬을 모두 적어도 한 번씩 방문할 때까지 섬 사이를 이동할 것이다.
농부 존의 헬리콥터는 연료가 얼마 남지 않아서, 소들이 집에 돌아가기로 할 때까지는 헬리콥터를 쓰고 싶지 않다. 다행히 격자의 일부 칸은 'S'로 표시된 얕은 물이다. 베시는 섬 사이를 이동하기 위해 이 칸들을 네 방위(북, 동, 남, 서)로 헤엄쳐 지나갈 수 있다. 또한 섬에서 얕은 물로, 그리고 그 반대로도 (네 방위로) 이동할 수 있다.
베시가 모든 섬을 방문하기 위해 헤엄쳐야 하는 최소 거리를 구하시오. (베시가 헤엄쳐야 하는 거리는 그녀가 'S'로 표시된 칸 위에 있는 서로 다른 횟수이다.) 지역의 지도를 살펴본 베시는 이것이 가능하다는 것을 알고 있다.
문제 제공: Neal Wu, 2007
첫째 줄: 공백으로 구분된 두 정수 R와 C.
둘째 줄부터 R+1번째 줄까지: i+1번째 줄에 격자의 i번째 행을 나타내는 C개의 문자가 주어진다. 깊은 물 칸은 '.', 섬 칸은 'X', 얕은 물 칸은 'S'로 표시된다.
첫째 줄: 베시가 모든 섬을 방문하기 위해 헤엄쳐야 하는 최소 거리를 나타내는 정수 하나.
island.in · 출력을 쓸 파일 island.out5 4
XX.S
.S..
SXSS
S.SX
..SX3Input details: There are three islands with shallow water paths connecting some of them.
Output details: Bessie can travel from the island in the top left to the one in the middle, swimming 1 unit, and then travel from the middle island to the one in the bottom right, swimming 2 units, for a total of 3 units.