题目描述

农夫约翰带着奶牛们到海上度假！奶牛们居住在 R × C 网格（1 ≤ R, C ≤ 50）中的 N（1 ≤ N ≤ 15）个岛屿上。岛屿被定义为网格上标记为'X'的最大连通区域，其中两个'X'如果共享一条边（上下左右）则被认为是连通的。（注意：对角相邻的'X'不一定连通）

贝茜来得比较晚，所以她将和约翰乘坐直升机抵达。因此她可以选择任意一个岛屿作为起点。她希望至少访问所有岛屿各一次，因此需要在岛屿之间旅行，直到所有 N 个岛屿都被访问过至少一次。

约翰的直升机燃料所剩不多，所以在奶牛们决定回家之前他不想再使用直升机。幸运的是，网格中有些方格是浅水区，标记为'S'。贝茜可以通过在四个基本方向（北、东、南、西）上游过这些'S'方格来在岛屿间移动。她也可以在岛屿和浅水区之间移动（同样通过四个基本方向）。

请计算贝茜为了访问所有岛屿至少一次需要游泳的最短距离。（贝茜的游泳距离是指她经过的'S'方格的不同数量）根据该区域的地图，贝茜知道这一定是可行的。

输入格式

• 第 1 行：两个空格分隔的整数 R 和 C
• 第 2 到 R+1 行：每行包含 C 个字符，描述网格的一行：
  • '.' 表示深水区
  • 'X' 表示岛屿
  • 'S' 表示浅水区

输出格式

• 第 1 行：一个整数，表示贝茜访问所有岛屿需要游泳的最短距离

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

3

样例解释

样例中有三个岛屿，部分岛屿间有浅水路径相连。

贝茜的最佳旅行路线：

1. 从左上角的岛屿出发
2. 游泳1个单位到达中间的岛屿
3. 再游泳2个单位到达右下角的岛屿 总共游泳距离为3个单位。