[USACO13JAN] Island Travels G
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.
题目描述
农夫约翰带着奶牛去海边度假了。
奶牛们住在 个岛屿上（），这些岛屿位于 的方格矩阵中（）。
岛屿是标记为 X 的方格，如果两个 X 共享一条边，则这两个 X 是相连的。（因此，共享一个角的两个 X 不一定相连）
然后，贝茜来晚了，所以她要和约翰一起乘坐直升飞机过去。
她可以选择任何一个岛屿并首先到达该岛。
她想看望每头奶牛至少一次，因此，她需要在岛屿之间旅行，直到她去过每个岛屿至少一次为止。
由于约翰的直升飞机燃料快用完了，所以直到奶牛们玩够了回家之前，他都不想动用这架飞机。
幸运的是有一些方格区域是浅水区，用 S 表示。
贝茜可以在浅水区沿四个基本方向游动，以便在各岛之间穿行。
她还可以在岛屿和浅水区之间沿四个基本方向行进，反之亦然。
请求出贝茜为了成功抵达所有岛屿所需要的最短游泳距离。
游泳距离是指贝茜在行进过程中到达标有 S 的方格区域的次数。
看完该地区的地图后，贝茜知道自己一定能成功抵达所有岛屿。
输入格式
第一行包含两个整数 和 。
接下来 行，每行包含 个字符用来描述方格矩阵。字符 . 表示深水方格区域，X 表示岛屿方格区域，S 表示浅水方格区域。
输出格式
输出贝茜为了成功抵达所有岛屿所需要的最短游泳距离。
5 4
XX.S
.S..
SXSS
S.SX
..SX
3
提示
贝茜可以在左上角岛屿着陆，然后按照右、下、下、右、右、下、下的方式行进，抵达所有岛屿。
期间共处于 S 方格中 次。