A22496.海岛旅行

提高+/省选-

USACO

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

给你一张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 
    

说明/提示

有三个岛屿,其中一些岛屿有浅水路径连接。

贝茜可以从左上角的岛屿旅行到中间的岛屿,游泳 1 个单位,然后从中间的岛屿旅行到右下角的岛屿,游泳 2 个单位,总共 3 个单位。

首页