问题描述

高桥君想一个人从学校走夜路回家。他所住的城市呈长方形的形状，被划分成了网格区块。他可以每秒沿着东西南北方向移动一个区块。每个区块都有一个日照度参数，可以用经过时间 $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}$

• 第一行给出整数 $N(1≦N≦500)$ 和整数 $M(1≦M≦500)$，分别表示城市的南北长度和东西长度，两个数字间以空格分隔。
• 接下来 $N$ 行，给出了网格城市中每个区块的状态 $c_{ij}$，分别为 s, g, 1-9, # 中的一种。
• 第 $i+1$ 行第 $j$ 个字符 $c_{ij}$ 描述了坐标 $(j,i)$ 处的状态，具体代表如下：
  • s : 该区块是学校。
  • g : 该区块是家。
  • 1-9 : 该区块的日照度。
  • # : 该区块不可进入。
• 不能经过输入给出城市的外部。
• 学校和家各有一个，且学校和家不相邻。

输出

输出**“路径亮度”**的最大值，计算结果保留六位小数并以一行输出。若不存在从学校到家的路径，请输出 -1。

输入示例 1

3 3
s52
743
32g

输出示例 1

2.910897

• 时间 $t=0$：从学校 $(1,1)$ 出发。
• 时间 $t=1$：移动到 $(2,1)$。由于时间 $t=1$，日照度 = $7$，因此 $(2,1)$ 的亮度为 $6.93$。
• 时间 $t=2$：移动到 $(2,2)$。由于时间 $t=2$，日照度 = $4$，因此 $(2,2)$ 的亮度为 $3.9204$。
• 时间 $t=3$：移动到 $(2,3)$。由于时间 $t=3$，日照度 = $3$，因此 $(2,3)$ 的亮度为 $2.910897$。
• 时间 $t=4$：到达家 $(3,3)$。在这之前，最暗的是时间 $t=3$ 时 $(2,3)$ 处的亮度 $2.910897$，因此答案为 $2.910897$。

输入示例 2

4 6
g31784
621415
627914
7451s3

输出示例 2

2.97

• 经过如下路径，亮度为 $2.97$，这是最佳选择。

Source Name

ARC 003