分数: 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