Island Travels

Farmer John has taken the cows on an ocean vacation! The cows live on $N$ ($1 \le N \le 15$) islands laid out on an $R \times C$ grid ($1 \le R, C \le 50$). An island is a maximal connected group of grid squares marked X, where two X squares are connected when they share a side. (So two X squares that only touch at a corner are not necessarily connected.)

Bessie arrives late and comes in by helicopter, so she may first land on any island she chooses. She wants to visit every cow at least once, so she will travel between islands until she has set foot on all $N$ islands.

Farmer John is low on fuel and will not fly again until it is time to go home. Luckily, some squares are shallow water, marked S. Bessie can swim through shallow-water squares in the four cardinal directions (north, east, south, west) to move between islands. She can also step between an island square and an adjacent shallow-water square, and vice versa. She can never enter a deep-water square, marked ..

Find the minimum distance Bessie must swim to visit all of the islands. The swim distance is the number of distinct times she stands on a square marked S. Bessie has studied the map and knows that visiting every island is possible.

• Line 1: two space-separated integers $R$ and $C$.
• Lines 2 to $R+1$: line $i+1$ contains $C$ characters giving row $i$ of the grid. Deep-water squares are ., island squares are X, and shallow-water squares are S.

• Line 1: a single integer, the minimum distance Bessie must swim to visit every island.

In the example there are three islands linked by shallow-water paths. Bessie can start on the island in the top-left corner, swim $1$ square to reach the middle island, then swim $2$ more squares to reach the island in the bottom-right corner, for a total of $3$.