SP3894 BOBALLS - Bouncing Balls

设想一个大小为 $N \times M$ 的网格。网格的左上角坐标为 $(0,0)$，右下角坐标为 $(N-1,M-1)$。每个格子上要么摆放着一个平台，要么写有一个数字。有两个球从网格顶部开始下落（位置分别为 $(0,Y1)$ 和 $(0,Y2)$，其中 $0 \leq Y1, Y2 < M$）。球在下落时只会垂直向下，除非它到达底行或碰到下方的平台。当球遇到平台时，它会随机向左或向右滚动，概率相等。球的得分是它经过的所有格子上的数字之和（包括起始格子）。但是，如果两个球都经过同一个格子，这个格子的分数只能算一次。目标是选择恰当的 $Y1$ 和 $Y2$，使得两个球的期望得分最大化。以下是一个网格示例（P 代表一个平台）： ``` N = 6, M = 6 112214 211243 30PPP2 423378 1P9753 220102 ``` 例如，从位置 $(0,3)$ 放下一个球，会出现以下三种得分情况： ``` 1) 2 + 2 + 1 + 1 + 0 + 2 + 4 + 1 + 2 = 15 2) 2 + 2 + 1 + 1 + 0 + 2 + 3 + 9 + 0 = 20 3) 2 + 2 + 4 + 3 + 2 + 8 + 3 + 2 = 26 ``` 考虑一个球的期望得分为： `1/2 * (1/2 * 15 + 1/2 * 20) + 1/2 * 26`

第一行输入为测试用例的数量。 每个测试用例的第一行包含两个整数 $N$ 和 $M$，分别表示网格的行数和列数。 接下来的 $N$ 行，每行包含 $M$ 个字符。每个字符要么是从 $0$ 到 $9$ 的数字，要么是字母 'P'。

输出最大期望得分，保留到小数点后四位。

$$1 \leq N, M \leq 100$$ **本翻译由 AI 自动生成**