P16584 [GKS 2016 #C] Monster Path

Codejamom 是一款手机游戏，玩家（怪物训练师）在现实世界中走动捕捉怪物。你有一部电池续航时间较短的旧智能手机，因此需要仔细选择路径，以尽可能多地捕捉怪物。 假设 Codejamom 的世界是一个 $R$ 行 $C$ 列的矩形网格。行从上到下编号，从 $0$ 开始；列从左到右编号，从 $0$ 开始。你从第 $R_S$ 行、第 $C_S$ 列的格子出发。你总共会走 $S$ 个单位步数；每一步必须移动到与你当前格子共享一条边（不仅仅是角）的相邻格子。 每当你步入一个尚未捕捉过怪物的格子时，如果该格子有“怪物吸引器”，你将以概率 $P$ 捕捉到该格子中的怪物，否则以概率 $Q$ 捕捉。如果成功捕捉到了该格子中的怪物，则怪物会消失，之后即使再次访问该格子也无法再捕捉任何怪物。如果未能捕捉到，你可以在以后再次访问该格子时继续尝试捕捉。起始格子是特殊的：在迈出第一步之前，你在那里没有任何捕捉怪物的机会。 如果你在行动之前就规划好最优路径，那么你所能捕捉到的怪物期望数最大是多少？ 电池只能支持有限的步数，所以请尽快作答！

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。 每个测试用例的第一行包含五个整数：$R$、$C$、$R_S$、$C_S$ 和 $S$。$R$ 和 $C$ 分别是网格的行数和列数；$R_S$ 和 $C_S$ 是你的起始位置的行号和列号；$S$ 是允许你走的步数。 下一行包含两个小数 $P$ 和 $Q$，其中 $P$ 是带有怪物吸引器的格子中遇到怪物的概率，$Q$ 是没有怪物吸引器的格子中遇到怪物的概率。$P$ 和 $Q$ 均精确到小数点后四位。 接下来的 $R$ 行，每行包含 $C$ 个由空格分隔的字符；第 $i$ 行的第 $j$ 个字符表示第 $i$ 行第 $j$ 列的格子。每个字符要么是 `.`（表示该格子没有吸引器），要么是 `A`（表示该格子有吸引器）。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是在给定步数内玩家所能捕捉到的最大期望怪物数。 如果 $y$ 与正确答案的绝对误差或相对误差在 $10^{-6}$ 以内，则认为正确。

在样例 #1 中，最优路径之一为 $(0,0)\to(0,1)\to(0,2)\to(1,2)\to(2,2)\to(2,3)$。在这条路径上，你捕捉到怪物的期望数为 $0.2 + 0.2 + 0.2 + 0.8 + 0.2 = 1.6$。请记住，迈出第一步之前没有机会捕捉怪物，因此计算中只有五个概率，而不是六个。 在样例 #2 中，最优路径之一为 $(9,1)\to(9,2)\to(8,2)\to(8,3)\to(8,2)$。在这条路径上，你捕捉到怪物的期望数为 $0.1 + 0.6121 + 0.1 + 0.23743359 = 1.04953359$。由于我们接受与正确答案（$1.04953359$）的绝对或相对误差在 $10^{-6}$ 以内的结果，因此 $1.0495336$ 是可接受的。 ### 限制条件 $1 \le T \le 100$。 $0 \le R_S < R$。 $0 \le C_S < C$。 $0 \le Q < P \le 1$。 **小数据集（测试集 1 – 可见）** $1 \le R \le 10$。 $1 \le C \le 10$。 $0 \le S \le 5$。 **大数据集（测试集 2 – 隐藏）** $1 \le R \le 20$。 $1 \le C \le 20$。 $0 \le S \le 9$。 翻译由 DeepSeek V4 Pro 完成