时间限制：1秒　　内存限制：256M

---

【题目描述】

　　农夫约翰带着奶牛去海边度假了。
　　奶牛们住在 \(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 表示浅水方格区域。

【输出格式】

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

【输入输出样例1】

　Input

5 4 
XX.S 
.S.. 
SXSS 
S.SX 
..SX 

　Output

3

【样例说明】

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

【来源】

　　Mr.he