← 返回题目列表

AtCoder · past202012_k

K. 投球

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

分数: 6 点

警告

2020 年 12 月 27 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

您正在玩“击中目标”游戏 4 \times 4 网格。

广场 i从顶部开始的第行和 j- 从左边算起的第列包含一个目标,如果 S_{i, j} is #,如果 S_{i, j} is .。当您用球击中每个目标一次或多次时,您就赢得了比赛。

当你向某个方格扔球时 x,球飞到以下五个方格之一,每个方格都有概率 \dfrac{1}{5}: x 本身和垂直或水平相邻的四个方块 x。 (假设网格外有空的方块。)如果该方块包含目标,则球会击中它。

假设您在游戏过程中始终做出最优选择以最小化该值,那么赢得比赛之前的投掷次数的预期值是多少?

约束

  • S_{i,j} is . or #.
  • 至少一个字符 S_{i,j} is #.

输入

输入由标准输入按以下格式给出:

S_{1,1}S_{1,2}S_{1,3}S_{1,4}
S_{2,1}S_{2,2}S_{2,3}S_{2,4}
S_{3,1}S_{3,2}S_{3,3}S_{3,4}
S_{4,1}S_{4,2}S_{4,3}S_{4,4}

输出

打印抛出次数的最小预期值。

如果您的输出与正确答案的绝对或相对误差最多为 10^{-6}.


示例输入 1

#...
....
....
....

示例输出 1

5.0000000000

击中目标之前的预期投掷次数为 5。请注意,球可能会错过网格。


示例输入 2

#...
#...
....
....

示例输出 2

7.5000000000

直到球击中两个目标之一时,我们将瞄准上面的目标,然后我们将瞄准剩下的目标。


示例输入 3

.#..
#.#.
.#..
....

示例输出 3

10.4166666667

一开始,瞄准四个目标中心的空方块是最佳的。


示例输入 4

###.
####
####
####

示例输出 4

32.5674089515