22554번 - スプリング・タイル 스페셜 저지다국어

ある朝、あなたが目覚めると、そこはバネだらけの迷宮の中だった。

なぜ自分がこんな見知らぬ場所にいるのかはわからない。この場でじっと助けを待つという選択肢も あるにはあるが、こういった迷宮の中に長居していると、いつかは必ず突風が吹いてきて吹き飛ばさ れてしまうことを、あなたは経験上知っていた。しかし、突風が吹いてくるまでの時間は判断のしよ うがない。そこであなたは、迷宮から脱出するまでに必要な移動回数の期待値が最小になるように行 動するのが最善の戦略だと考えた。

足元に落ちていた正体不明の巻物を拾ってためしに読んでみたところ、偶然にも迷宮の全体マップを 知覚することができた。さらに、たまたま持っていた草を飲むことで、すべてのワナの位置も知るこ とができた。どうやらこの迷宮には、危険なモンスターやバネ以外のワナは存在しないらしい。

この迷宮は、いくつかの種類のタイルが長方形に並んだ形をしており、たとえば以下のようにあらわ される。

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

• 「.」：床。この上なら自由に歩き回ることができる。
• 「#」：壁。あなたは壁の中に入ることはできない。
• 「s」：あなたの最初の位置。このタイルの下は床になっている。
• 「g」：階段。このタイルの上に乗れば、迷宮を脱出したことになる。
• 「*」：バネ。このタイルの上に乗ると、いずれかの床の上（階段、バネのタイルは除く）にランダムに飛ばされる。それぞれの床に飛ばされる確率はすべて等しい。

タイルの種類は、この５つのいずれかである。

あなたは、現在乗っているタイルから隣り合ったタイルへ、上下左右いずれかの方向に１マスずつ移 動することができる。ただし、ナナメに移動することはできない。

迷宮のマップが与えられたとき、最善の戦略をとった場合に迷宮から脱出するまでに必要な移動回数 の期待値を求めよ。バネで飛ばされるのは移動回数には含めない。

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

入力の１行目には、整数W（3 ≤ W ≤ 500）と整数H（3 ≤ H ≤ 500）が、この順に空白区切りで書かれている。整数W は迷宮の横幅を、整数H は迷宮の縦幅をあらわす。

続くH 行には、迷宮のマップをあらわすW 個の文字が書かれている（空白区切りではない）。この部分の形式は、先に挙げた例のとおりである。なお、データ中に「s」と「g」は、それぞれちょうど１回ずつ出現する。また、迷宮の周囲１マスは、必ず壁で囲まれている。

なお、与えられる迷宮では、どのように移動し、バネでどのように飛ばされたとしても、「バネで飛 ばされる床を任意に設定できたとしても脱出不可能な状態」に陥ることはないと仮定してよい。

最善の戦略をとったときに、脱出までにかかる移動回数の期待値を出力せよ。出力は誤差を含んでい てもよいが、真の値との相対誤差が10^-9 未満でなければならない。