P3070 [USACO13JAN] Island Travels G

农夫约翰带着奶牛去海边度假了。 奶牛们住在 $N$ 个岛屿上（$1 \le N \le 15$），这些岛屿位于 $R \times C$ 的方格矩阵中（$1 \le R,C \le 50$）。 岛屿是标记为 `X` 的方格，如果两个 `X` 共享一条边，则这两个 `X` 是相连的。（因此，共享一个角的两个 `X` 不一定相连） 然后，贝茜来晚了，所以她要和约翰一起乘坐直升飞机过去。 她可以选择任何一个岛屿并首先到达该岛。 她想看望每头奶牛至少一次，因此，她需要在岛屿之间旅行，直到她去过每个岛屿至少一次为止。 由于约翰的直升飞机燃料快用完了，所以直到奶牛们玩够了回家之前，他都不想动用这架飞机。 幸运的是有一些方格区域是浅水区，用 `S` 表示。 贝茜可以在浅水区沿四个基本方向游动，以便在各岛之间穿行。 她还可以在岛屿和浅水区之间沿四个基本方向行进，反之亦然。 请求出贝茜为了成功抵达所有岛屿所需要的最短游泳距离。 游泳距离是指贝茜在行进过程中到达标有 `S` 的方格区域的次数。 看完该地区的地图后，贝茜知道自己一定能成功抵达所有岛屿。

第一行包含两个整数 $R$ 和 $C$。 接下来 $R$ 行，每行包含 $C$ 个字符用来描述方格矩阵。字符 . 表示深水方格区域，`X` 表示岛屿方格区域，`S` 表示浅水方格区域。

输出贝茜为了成功抵达所有岛屿所需要的最短游泳距离。

贝茜可以在左上角岛屿着陆，然后按照右、下、下、右、右、下、下的方式行进，抵达所有岛屿。 期间共处于 `S` 方格中 $3$ 次。