← 返回题目列表

AtCoder · arc003_3

C. 摸黑回家的路上

中文机器翻译题面 查看原题

問題文

高桥晚上从学校步行回家。 1 我正在尝试和一群人一起回家。
他居住的小镇呈长方形,被划分为网格状的部分。他是东、西、南、北 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 和 在 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 ,这是最好的。