Jack和Jill

Jack 和 Jill 互相不喜欢对方，甚至在上学途中也不想遇见彼此。请你为他们分别安排一条从家到学校的路线，使得上学过程中两人之间的最短距离尽可能大。

地图是一个 $N\times N$ 的方格矩阵。从一个格子移动到相邻格子需要花费 $1$ 个单位时间。两人同时从各自家中出发，前往各自的学校，途中不能停留。每次移动后，两人所在格子中心点之间的欧氏距离即为该时刻两人之间的距离。

地图上存在无法进入的格子。此外，Jack 的家和学校对 Jill 而言不可进入，Jill 的家和学校对 Jack 而言同样不可进入。

请计算所有可行路线安排中，两人之间最短距离的最大值。

输入格式

第一行输入一个整数 $N$ ，表示地图的边长。

接下来 $N$ 行，每行包含 $N$ 个字符，描述方格地图。字符含义如下：

输出一个实数，表示最优路线安排中两人之间的最短距离，保留两位小数。

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

6.71

本题题面与测试数据整理自 BZOJ。

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

6.71