题目描述

农夫约翰带着奶牛去海边度假了。

奶牛们住在 $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 表示浅水方格区域。

输出格式

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

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

3 

提示

贝茜可以在左上角岛屿着陆，然后按照右、下、下、右、右、下、下的方式行进，抵达所有岛屿。

期间共处于 S 方格中 $3$ 次。