农夫约翰带着奶牛去海边度假了！奶牛生活在N个（1<=N<=15）岛屿上，这些岛屿位于R x C网格（1<=R，C<=50）上。岛是网格上标记为“X”的最大连通正方形组，如果两个“X”共享一条边，则它们是连通的。（因此，共享一个角的两个“X”不一定是连接的。）
然而，贝茜来晚了，所以她要和FJ一起乘直升机进来。因此，她可以首先降落在她选择的任何岛屿上。她想至少参观一次所有的奶牛，所以她将在岛屿之间旅行，直到她至少参观了所有N个岛屿一次。
有’S’,’X’,’.’三种地形，所有判定相邻与行走都是四连通的。我们设’X’为陆地，一个’X’连通块为一个岛屿，’S’为浅水，’.’为深水。刚开始你可以降落在任一一块陆地上，在陆地上可以行走，在浅水里可以游泳。并且陆地和浅水之间可以相互通行。但无论如何都不能走到深水。你现在要求通过行走和游泳使得你把所有的岛屿都经过一边。Q：你最少要经过几格子浅水区？保证有解。
第1行：两个空格分隔的整数：R和C。
*第2..R+1行：第i+1行包含C字符，表示网格的第i行。深水方块标记为“.”，岛屿方块标记为“X”，浅水方块标记为”S“。
一个整数表示贝西游遍所有岛屿所需的最小距离。
5 4 XX.S .S.. SXSS S.SX ..SX
3
对于所有数据，保证，1\le n\le20,1\le x_i,y_i\le10^4,1\le D\le10^5。
USACO