스프링 타일

어느 아침, 눈을 떴더니 온통 스프링투성이인 미로 속이었다.

왜 이런 낯선 곳에 있는지는 모른다. 가만히 앉아 구조를 기다리는 선택지도 없지는 않지만, 이런 미로 안에 오래 머물다 보면 언젠가는 반드시 돌풍이 불어와 날아가 버린다는 사실을 경험으로 알고 있었다. 그러나 돌풍이 언제 불어올지는 판단할 방법이 없다. 그래서 미로에서 탈출할 때까지 필요한 이동 횟수의 기댓값이 최소가 되도록 행동하는 것이 최선의 전략이라고 생각했다.

발밑에 떨어져 있던 정체불명의 두루마리를 주워 시험 삼아 읽어 보니, 우연히도 미로 전체 지도를 알 수 있었다. 게다가 마침 가지고 있던 약초를 먹어 모든 함정의 위치도 알게 되었다. 이 미로에는 위험한 몬스터와 스프링 외에 다른 함정은 없는 모양이다.

미로는 여러 종류의 타일이 직사각형으로 늘어선 형태이며, 예를 들어 다음과 같이 나타낸다.

########
#..##g.#
#*#.*#.#
#......#
#*s#*.*#
########

• .: 바닥. 이 위에서는 자유롭게 걸어 다닐 수 있다.
• #: 벽. 벽 안으로 들어갈 수 없다.
• s: 처음 위치. 이 타일 아래는 바닥이다.
• g: 계단. 이 타일 위에 올라서면 미로에서 탈출한 것이다.
• *: 스프링. 이 타일 위에 올라서면 어느 바닥 위로든(계단 타일과 스프링 타일은 제외) 무작위로 튕겨 나간다. 각 바닥으로 튕겨 나갈 확률은 모두 같다.

타일 종류는 이 다섯 가지 중 하나이다.

현재 올라 있는 타일에서 인접한 타일로 상하좌우 중 한 방향으로 한 칸씩 이동할 수 있다. 대각선으로는 이동할 수 없다.

미로 지도가 주어졌을 때, 최선의 전략을 취했을 경우 미로에서 탈출할 때까지 필요한 이동 횟수의 기댓값을 구하라. 스프링으로 튕겨 나가는 것은 이동 횟수에 포함되지 않는다.

W H
c11 c12 ... c1w
c21 c22 ... c2w
::    :
ch1 ch2 ... chw

입력의 첫 줄에는 정수 $W$ ($3 \le W \le 500$)와 정수 $H$ ($3 \le H \le 500$)가 이 순서로 공백을 사이에 두고 주어진다. 정수 $W$는 미로의 가로 길이, 정수 $H$는 미로의 세로 길이를 나타낸다.

이어지는 $H$줄에는 미로 지도를 나타내는 $W$개의 문자가 주어진다(공백으로 구분되지 않는다). 이 부분의 형식은 앞에 든 예와 같다. 데이터에서 s와 g는 각각 정확히 한 번 나타난다. 또한 미로의 둘레 한 칸은 반드시 벽으로 둘러싸여 있다.

주어지는 미로에서는 어떻게 이동하고 스프링으로 어떻게 튕겨 나가더라도, 스프링으로 튕겨 나가는 바닥을 임의로 설정할 수 있다고 해도 탈출할 수 없는 상태에 빠지지 않는다고 가정해도 좋다.

최선의 전략을 취했을 때 탈출까지 걸리는 이동 횟수의 기댓값을 출력하라. 출력에는 오차가 포함되어도 되지만, 참값과의 상대오차가 $10^{-9}$ 미만이어야 한다.