← 返回题目
题库练习 海岛旅行
← 上一题 下一题 →

A2785 | 海岛旅行

来源USACO / 2013
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给你一张r*c的地图，有’S’,’X’,’.’三种地形，所有判定相邻与行走都是四连通的。我们设’X’为陆地，一个’X’连通块为一个岛屿，’S’为浅水，’.’为深水。刚开始你可以降落在任一一块陆地上，在陆地上可以行走，在浅水里可以游泳。并且陆地和浅水之间可以相互通行。但无论如何都不能走到深水。你现在要求通过行走和游泳使得你把所有的岛屿都经过一边。Q：你最少要经过几个浅水区？保证有解。

输入格式

* 第 1 行：两个空格分隔的整数：R 和 C。

* 第 2..R+1 行：第 i+1 行包含 C 字符，给出网格的第 i 行。深水方块标记为“.”，岛屿方块标记为“X”，浅水方块标记为“S”。

输出格式

* 第 1 行：单个整数，表示 Bessie 必须游泳才能访问所有岛屿的最小距离

输入输出样例

输入 #1
5 4 
XX.S 
.S.. 
SXSS 
S.SX 
..SX
输出 #1
3
C++ 编辑器
输入
输出