【迷宫花园】

题目描述

给定一个一定存在从起点到终点的路径的四联通迷宫。已知 Tar 左右方向移动的时间为 1 ,上下移动的时间为未知实数 v 。求当 Tar 从起点到终点的最短移动时间为已知实数 L 时,未知实数 v 是多少。

输入格式

输入数据包含多个测试点。第一行为一个整数 T ,表示测试点的数目。
对于每一个测试点,第一行包含实数 L 和两个整数 R,C。R 为迷宫的上下长度,C 为迷宫的左右长度。
之后的 R 行,每行包含 C 个字符。其中空格表示空地,S 表示起点,E 表示终点,# 表示围墙。

输出格式

对于每一个测试点,在单独的一行内输出未知实数 v ,输出保留 5 位小数。

样例数据 1

输入

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

样例看着很奇怪……复制到记事本上看吧

输出

0.50000
0.21053

备注

【数据范围】
20% 的数据,1≤R,C≤10。
100% 的数据,1≤R,C≤100;0≤v<10。

二分答案+SPFA

首先二分v,然后把v带进去每次求一遍到终点的最短路,看是否能进行更新,然后分啊分就分出答案来了……

不过我还是得吐槽一句,这道题有毒啊!一不小心double就写成int无限WA,队列大一点就TLE TLE TLE关键是一定记住加载cmath不然CE哭……

下面是代码:

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

3 Comments

  • image

    样例才是有毒 ➡
    话说我考试的时候样例死活读不进来,后来手打了一次才好,旁边的人也是这症状…

      image

      @YYY 其实scanf读单个char挺麻烦的……还要注意开始读完L R C后要\n不然读不进去,所以说
      cin大法好!!!

        image

        @UNknown 然而我就是cin读的,而且不是字符读不进,而是连开头那个整数n都读不进!!!

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*