#1191. 2195. Jack和Jill

2195. Jack和Jill

#2195. Jack和Jill

题目描述

Jack和Jill互相不喜欢对方,甚至在上学的时候也不想遇到对方。他们请你帮他们安排上学的路线,使得在上学过程中,他们之间的最短距离最长。给你一个N*N的格子地图,从一个格子移到另一个相邻的花费一个单位时间。所谓在任何时刻的距离指每次移动后他们所在格子的中心点的距离。他们各自从家中出发,去各自学校。中途不休息,地图上有些点不能到达的,当然Jack的家和学校对于Jill也是不可到达的,反之亦然.

输入格式

第一行给出数字N,N< = 30 接下来NN的字符矩阵,可能有以下字符。 'H'代表Jack的家. 'S'代表Jack的学校 'h'及's'代表Jill有家和学校. ''代表公共的不可到达点 '.'代表空地

输出格式

输出一个数字,代表你的方案中他们之间的最短距离,保留两位小数.

样例

样例输入

10  

..........  

...H......  

.**...s...  

.**.......  

.**.......  

.**.......  

.**.......  

.**.......  

...S..h..*  

..........  

样例输出

6.71  

数据范围与提示