잭과 질

언덕에서 있었던 사건 이후로 잭과 질은 서로를 싫어하게 되어, 등굣길 내내 되도록 멀리 떨어져 있고 싶어 한다. 두 사람은 매일 학교에 가야 하는데, 잭은 남학교에, 질은 여학교에 다니며 두 학교는 같은 시각에 수업을 시작한다. 당신은 두 사람의 경로와 일정을 짜서, 등교하는 동안 매 순간 잭과 질 사이의 직선거리 중 가장 가까웠던 값(최소 직선거리)을 최대가 되도록 만드는 일을 맡았다.

마을은 $n \times n$ 크기의 정사각 격자이다($n \le 30$). 한 칸에서 상하좌우로 인접한 칸으로 걸어가는 데 1분이 걸린다. 거리를 따질 때는 두 사람이 매 분에 머무는 격자 칸의 위치만 고려하면 되고, 칸과 칸 사이를 이동하는 중간 지점은 고려하지 않는다. 강이나 건물 등으로 인해 지나갈 수 없는 칸도 있다.

잭은 자기 집에서 출발해 학교에 도착할 때까지 멈추지 않고 계속 걷는다. 질도 잭과 같은 분에 자기 집에서 출발해 학교에 도착할 때까지 계속 걷는다. 잭의 집과 학교는 질이 지나갈 수 없고, 질의 집과 학교는 잭이 지나갈 수 없다. 학교에 먼저 도착한 사람은 그 자리에 그대로 머문다. 두 사람 모두 지나갈 수 없는 그 밖의 칸은 입력으로 주어진다. 경로는 반드시 최단 경로일 필요는 없으며(더 길게 돌아갈 수 있다), 두 사람의 이동 시간은 서로 달라도 된다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 정수 $n$이 적힌 한 줄로 시작하고, 이어서 마을 지도를 나타내는 $n$개의 줄이 주어지며 각 줄은 $n$개의 문자로 이루어진다. 지도의 각 문자는 다음을 뜻한다.

• H — 잭의 집
• S — 잭의 학교
• h — 질의 집
• s — 질의 학교
• * — 두 사람 모두 지나갈 수 없는 칸
• . — 그 밖의 지나갈 수 있는 칸

지도의 위쪽이 북(N), 왼쪽이 서(W)인 일반적인 방위 규약을 따른다. 마지막 테스트 케이스 다음에는 0만 적힌 줄이 온다.

각 테스트 케이스마다 한 줄에, 등교하는 전체 일정 동안 잭과 질 사이의 가장 가까운 직선거리를 최대로 만들었을 때 그 값을 출력한다. 값은 소수점 아래 정확히 둘째 자리까지 반올림하여 출력한다. 항상 적어도 하나의 유효한 경로 쌍이 존재함이 보장된다.