P3070 [USACO13JAN] Island Travels G

Farmer John has taken the cows to a vacation out on the ocean! The cows are living on N (1

\* Line 1: Two space-separated integers: R and C. \* Lines 2..R+1: Line i+1 contains C characters giving row i of the grid. Deep water squares are marked as '.', island squares are marked as 'X', and shallow water squares are marked as 'S'.

\* Line 1: A single integer representing the minimum distance Bessie has to swim to visit all islands.

There are three islands with shallow water paths connecting some of them. 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.