問題文
他居住的小镇呈长方形,被划分为网格状的部分。他是东、西、南、北 1 以秒为单位 1 您可以逐个移动部分。
每个地块都有阳光和经过的时间 t 秒(出发时间为 0 秒)“各部分的亮度” = 阳光充足 × 0.99^t”。
在您放学回家途中经过的路线部分。“车厢的亮度” 该路线上的最小值为“路线亮度”。
高桥害怕黑暗, 我们希望选择“路线亮度”尽可能大的路线。
如果您选择这样的路线, 查找“路线亮度”。
入力
N M
c_{11}c_{12}…c_{1M}
c_{21}c_{22}…c_{2M}
:
:
c_{N1}c_{N2}…c_{NM}
- 1 Row 是一个整数,表示城市的南北长度。 N(1≦N≦500) 和一个整数作为东西向长度 M(1≦M≦500) 用空格分隔。
- 2 从行 N 行表示网格状城市的每个部分的状态。 c_{ij} 分别
s,g,1-9,#。 - i+1 行目 j 字符数 c_{ij} 是坐标 (j,i) 表示以下状态。
s:表示该区域是一所学校。g:表示该部分是您的家。1-9:表示该区域的阳光明媚程度。#:表示该区域不能进入。
- 无法通过给定城市之外。
s和 在g分别是 1 由下式给出s和 在g不相邻。
出力
如果没有从学校回家的路线
-1 和
在 1 行。误差至少是绝对误差和相对误差之一。 1e−9 如果低于则允许。
请在末尾输出换行符。 离开
入力例 1
3 3 s52 743 32g
出力例 1
2.910897
- 時刻0: 学校 (1,1) 。 转至
- 時刻1: (2,1) 。时间 t=1, 阳光充足=7 所以,(2,1) 的亮度为 6.93 。
- 時刻2: (2,2) 。时间 t=2, 阳光充足=4 所以,(2,2) 亮度为 转至 3.9204 。
- 時刻3: (2,3) 。时间 t=3, 阳光充足=3 所以,(2,3) 亮度为 转至 2.910897 。
- 時刻4: 自宅 (3,3) 。迄今为止最黑暗的时刻是时候 t=3 的 (2,3) 处的亮度 2.910897 所以答案是 2.910897 。
入力例 2
4 6 g31784 621415 627914 7451s3
出力例 2
2.97
- 当走以下路线时,亮度可能会变差 2.97 ,这是最好的。