题目名称	777. [Violet 1] 迷宫花园
输入输出	`mazev.in/out`
难度等级	★★★
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	王者自由于2012-04-19加入
开放分组	全部用户
提交状态
分类标签
	分享题解

通过：23，提交：110，通过率：20.91%
Sky_miner	100	0.221 s	0.46 MiB	C++
fullpower	100	0.222 s	8.56 MiB	C++
stdafx.h	100	0.223 s	0.37 MiB	C++
fullpower	100	0.226 s	8.56 MiB	C++
lalalala	100	0.227 s	1.33 MiB	C++
zys	100	0.270 s	1.64 MiB	C++
rpCardinal	100	0.317 s	0.43 MiB	C++
K1412	100	0.387 s	1.02 MiB	Pascal
K1412	100	0.392 s	0.92 MiB	Pascal
K1412	100	0.450 s	0.92 MiB	Pascal

关于迷宫花园的近10条评论(全部评论)
坑爹读入 AAAAAAAAAA 2017-10-27 10:59 4楼
本地AC 上去全Wa 替我问候一下这评测机！！！！！！！！！！这还**怎么做题！！！！！！！！！！！！！！ Sky_miner 2016-10-12 16:19 3楼
我以为用整形会快一点……但事实证明为了保证精度开成longlong后更慢了…… 而且别听他胡说，这题没评侧插件= =！水中音 2015-03-18 16:33 2楼
精度問題坑爹啊～～～全都差0.00001啊 Makazeu 2012-04-19 21:40 1楼

777. [Violet 1] 迷宫花园

★★★ 输入文件：mazev.in 输出文件：mazev.out 评测插件
时间限制：1 s 内存限制：128 MiB

背景

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

题目描述

普通得甚至有些二逼的矮穷挫少年——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。