Jack and Jill

Time limit1sMemory limit128 MB

Summary

Choose walking routes and timing for two people on a grid so the smallest distance between them at any whole minute is as large as possible, and report that maximum.

Level: Hard9 of 10
Topics: Binary search, BFS, Graph, Shortest path
Solved: No attempts yet

Problem

Ever since the incident on the hill, Jack and Jill dislike each other and want to stay as far apart as possible on the way to school. Both must attend school every day — Jack goes to a boys' school and Jill to a girls' school — and both schools start at the same time. You have been hired to design two routes and a schedule so that the closest straight-line distance between Jack and Jill at any minute during the trip is as large as possible.

The town is an $n \times n$ square grid ( $n \le 30$ ). Walking from one cell to an adjacent cell (up, down, left, or right) takes one minute. When measuring the distance you only need to consider the grid cells the two occupy at each whole minute; you do not need to consider any intermediate point along the path between consecutive cells. Some cells are impassable because of rivers, buildings, and so on.

Jack starts at his house and walks without stopping until he reaches his school; Jill does the same, starting at the same minute as Jack. Jack's house and school are impassable to Jill, and Jill's house and school are impassable to Jack. Whoever reaches their school first stays there. All other cells that are impassable to both are given in the input. Routes need not be shortest paths (a longer, roundabout route is allowed), and the two travellers may take different amounts of time to arrive.

Input

The input consists of several test cases. Each test case begins with a line containing $n$ , followed by $n$ lines of $n$ characters each describing the town map. The characters mean:

H — Jack’s house
S — Jack’s school
h — Jill’s house
s — Jill’s school
* — a cell impassable to both
. — any other passable cell

Following the usual cartographic convention, North is at the top of the map and West is on the left. A line containing a single 0 follows the last test case.

Output

For each test case, output a single line containing the maximum achievable value of the closest straight-line distance between Jack and Jill over the whole schedule, rounded to exactly two decimal places. It is guaranteed that at least one valid pair of routes exists.

Examples3

Example 1

Input

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

Expected output

6.71

Example 2
Input
```
2
Hs
Sh
0
```
Expected output
```
1.41
```
Example 3
Input
```
5
H...h
.....
.....
.....
S...s
0
```
Expected output
```
4.00
```