OI题库

背景

我们常常迷失在这狗血的世界里。
拼命地向着目标努力，最后却总感觉有一只看不见的手在玩弄自己。
生活就像一个舞台，自己却不知道在给谁唱着哪一出折子戏。
有时候非常羡慕那些思想者，从古希腊的智者，一直到被称为“新亚里士多德学派”的人们，在嘈杂纷乱的世界里还能一直——或者说常常——清醒地知道自己的方向，尽管命运无情多变，他们也未自暴自弃。
可是我们呢，我们在做些什么？舞台上立起林林总总的道具，彩绘披帛间看不清当年倚门回首的那个梦，只听到遥远的观众席上起伏的喝彩或骂声，曲中谢幕时漫天散落的金币砸碎脑际里青涩少年的背影，生活变成一座迷宫，看不到出口，望不见尽头，而命运的大手还在无情地搬弄迷宫里的砖石——在你看到出口的时候立起一座墙，在你委顿不前的时候拆出一扇窗，最后只能坐倒在地痛哭流涕，然后再擦干眼泪默默爬起。
大概生活就是这样的轮回吧。命运的恶趣味。
拉马克主义坚信着环境终究会改变生命，并且让这种扭曲过的性状一代代传承下去。尽管生物学和社会学现在还算是两个截然不同的分支，但是这种解释性的哲言偶尔也会说明一些问题。恶趣味的命运造就了恶趣味的人，包括坐在屏幕前的你。当围观成为习惯，当调戏成为本能，这时面对一些必须服从在你的力量之下的弱小者，你也会不自禁地去戏弄他。

题目描述

普通得甚至有些二逼的矮穷挫少年——Dios ，不可避免地遇到了他生命中的劫数，白富美少女Nyution。但是按照正常的校园故事的发展，Nyution 是无论如何不会喜欢上各方面条件都差到不行的Dios 的。不过，Dios 还是面对Nyution颤抖着说出了那三个字。Nyution既不想过分地让Dios 伤心，又不想接受她根本看不上的 Dios ，于是决定让 Dios 走一个建在她家后院里的迷宫花园——如果Dios 能很快地从起点走到终点，证明他的聪明才智，Nyution就答应他的表白。
当然Nyution敢这么说肯定是有准备的。Nyution的花园可以看做一个迷宫，在迷宫内部有起点和终点。Dios 要从起点走到终点，并且他只能选择前后左右四个方向行走，而且显然不能走到篱笆上，也不能走出迷宫的边界。Nyution经过仔细的调查发现，Dios 移动到相邻格子的耗时肯定是1。同时，Nyution将在Dios 的挑战开始前，通过进行适当的路面调整，使Dios 在南北方向（数据中的上下方向）的移动时间由1 变成实数 v 。首先，Nyution不能让Dios 过快地到达终点，这样她就得接受表白；其次，Nyution也不想让 Dios 开了小宇宙之后还是过慢地到达终点，这样显得她在刁难Dios 。最后她确定了一个实数L ——就是最坏情况（也就是 Dios 最神勇威武耗时最短的情况）下，Dios 将花费L 的时间由起点到达终点。但是 Nyution显然不会求此时的 v 值，于是她找到了一向以算法达人著称的你。你当然不会拒绝白富美Nyution的请求，决定帮她算出此时的 v 。

由于Nyution不仅是白富美同时也是三好学生，所以她肯定不会给你一个无解的任务。并且，Nyution的迷宫中一定没有水平的从起点到终点的通路。

输入格式

输入文件包含多个测试点。第一行包含一个整数，表示测试点的数目。
每个测试点的第一行包含实数L 和两个整数R , C 。L 的含义如上，R 表示Nyution的花园南北方向的长度，C 表示花园东西方向的长度。
之后R 行为花园的描述，每行包含C 个字符。其中空格（ASCII 码为32）代表空地，S 代表起点，E 代表终点，#  代表篱笆。显然，起点和终点都是空地。

输出格式

对于每组测试数据，在单独的一行内输出v 的值，保留5 位小数。当你的答案与标准答案之差不超过 0.00002 时得分。

样例输入

2
2.5 4 5
#####
#S  #
#  E#
#####
21 13 12
############
#S##     #E#
# ##  #  # #
#   # #  # #
### # #  # #
#   # #  # #
#  ## #  # #
##  # #  # #
### # #  # #
##  # #  # #
#  ## #    #
#     #    #
############

样例输出

0.50000
0.21053

数据范围与约定

对于20% 的数据，满足 1<= C, R <=10。
对于另外 20%  的数据，保证答案 v 的小数部分为0，即 floor(v)=v 。
对于100%  的数据，满足 1<= C, R <=100 ，保证 0<= v <=10。