岛屿旅行
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
题目描述
农夫约翰带着奶牛们到海上度假！奶牛们居住在 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个单位到达右下角的岛屿 总共游泳距离为3个单位。
