A2785. 海岛旅行
编程题
提高+/省选-
知识点
题目描述
给你一张r*c的地图，有’S’,’X’,’.’三种地形，所有判定相邻与行走都是四连通的。我们设’X’为陆地，一个’X’连通块为一个岛屿，’S’为浅水，’.’为深水。刚开始你可以降落在任一一块陆地上，在陆地上可以行走，在浅水里可以游泳。并且陆地和浅水之间可以相互通行。但无论如何都不能走到深水。你现在要求通过行走和游泳使得你把所有的岛屿都经过一边。Q：你最少要经过几个浅水区？保证有解。
输入格式
* 第 1 行：两个空格分隔的整数：R 和 C。
* 第 2..R+1 行：第 i+1 行包含 C 字符，给出网格的第 i 行。深水方块标记为“.”，岛屿方块标记为“X”，浅水方块标记为“S”。
* 第 2..R+1 行：第 i+1 行包含 C 字符，给出网格的第 i 行。深水方块标记为“.”，岛屿方块标记为“X”，浅水方块标记为“S”。
输出格式
* 第 1 行：单个整数，表示 Bessie 必须游泳才能访问所有岛屿的最小距离
输入输出样例
输入 #1
5 4 XX.S .S.. SXSS S.SX ..SX
输出 #1
3
说明/提示
有三个岛屿，其中一些岛屿有浅水路径连接。
贝茜可以从左上角的岛屿旅行到中间的岛屿，游泳 1 个单位，然后从中间的岛屿旅行到右下角的岛屿，游泳 2 个单位，总共 3 个单位。
贝茜可以从左上角的岛屿旅行到中间的岛屿，游泳 1 个单位，然后从中间的岛屿旅行到右下角的岛屿，游泳 2 个单位，总共 3 个单位。