Jack and Jill

内存限制：162 MiB 时间限制：10 Sec

Jack和Jill互相不喜欢对方，甚至在每天上学的时候都不愿意碰到对方. Jack咬着牙说,”我希望离他越远越好”. 当然,Jill也是这么想的. 他们请你帮他们安排上学的路线，使得在途中任何时刻，他们之间的最短距离最长. 给你一个n*n的格子地图，从一个格子移动到相邻的格子花费1个单位时间.所谓的途中任何时刻的距离，是指每次移动之后他们俩所在格子的中心距离.Jack和Jill同时从各自家中出发，前往各自学校,而且中途不能休息.地图伤有一些不可到达的点，当然,Jack的家和学校对Jill来说是不可到达的点，当然Jill的家和学校对于Jack来说也是不可到达的.n<=30.

第一行一个整数N，N< = 30.表示地图的大小接下来一个N*N的字符矩阵，它可能出现下面字符 'H'代表Jack的家 'S'代表Jack的学校 'h'代表Jill的家 's'代表Jill的学校 '*'代表公共的不可到达的点 '.'代表空地

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

样例输入


			10

..........

...H......

.**...s...

.**.......

.**.......

.**.......

.**.......

.**.......

...S..h..*

..........

样例输出


			6.71

#1973. Jack and Jill

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示