题目描述

Jack 和 Jill 互相不喜欢对方，甚至在每天上学的时候都不愿意碰到对方。Jack 咬着牙说，“我希望离他越远越好”。当然，Jill 也是这么想的。他们请你帮他们安排上学的路线，使得在途中任何时刻，他们之间的最短距离最长。

给你一个 $n \times n$ 的格子地图，从一个格子移动到相邻的格子花费 $1$ 个单位时间。所谓的途中任何时刻的距离，是指每次移动之后他们俩所在格子的中心距离。Jack 和 Jill 同时从各自家中出发，前往各自学校，而且中途不能休息。地图伤有一些不可到达的点，当然，Jack 的家和学校对 Jill 来说是不可到达的点，当然 Jill 的家和学校对于 Jack 来说也是不可到达的。

输入格式

第一行一个整数 $n$，表示地图的大小。

接下来一个 $n \times n$ 的字符矩阵，它可能出现下面字符：

• H 代表 Jack 的家；
• S 代表 Jack 的学校；
• h 代表 Jill 的家；
• s 代表 Jill 的学校；
• * 代表公共的不可到达的点；
• . 代表空地。

输出格式

输出你的方案中他们两者之间的最短距离，保留两位小数。

10
..........
...H......
.**...s...
.**.......
.**.......
.**.......
.**.......
.**.......
...S..h..*
..........

6.71

数据规模与约定

对于 $100\%$ 的数据，$n \leq 30$。

题目来源

OIBH Online Programming Contest