P5531 [CCO 2019] Human Error

Justin 和 Donald 正在玩一种游戏：跳棋。你可能没有听说过，但是规则非常简单。 棋盘是一个矩形网格，在最开始时，每一格上恰好有一个棋子，并且每名玩家在棋盘上最少拥有一枚棋子。Justin 的棋子被标记为 `J`，而Donald的被标记为 `D`。 Justin 先下棋。在一次移动中，这位玩家可以移动自己的一枚棋子并吃掉相邻的一枚棋子**（不一定是对手的）**，随后轮到对手。如果当前玩家无法进行这样的操作，那么这位玩家就输了。 棋子 $A$ 与 $B$ 是相邻的，当且仅当 $A$ 正好在 $B$ 的上/下/左/右一格。 在理想的世界中，两人都是绝佳的逻辑学者，可以知晓每种棋盘上的最佳策略。然而这是不现实的。事实上，在游玩时，两人只会选择相对较好的走法。它到底有多好取决于 Justin 和 Donald 的误差常数，分别是 $J$ 和 $D$。 形式化地，拥有误差常数 $A$ 的玩家会从所有可能的走法中选择其中 $A$ 种组成方案集合。如果所有可能的走法数 $ P \le A $，那么方案集合仅包含这 $P$ 种。之后，这位玩家会随机（等概率）地挑选其中的一种并依此进行操作。 两人在挑选方案组成集合时总会选择最优的方案，亦知晓对手也会选择最优方案。 请问 Justin 获胜的概率是多少？

第一行两个正整数，$R$ 和 $C$（用空格隔开）。 之后 $R$ 行，每行 $C$ 个字符，代表初始棋盘上的棋子分布（含义见题目描述）。 之后一行两个正整数，$J$ 和 $D$（用空格隔开），含义见题目描述。

一行，一个精确到 $3$ 位小数的浮点数，代表 Justin 获胜的概率。

### 限制 $ 1 \le R \times C \le 13 $ $ 1 \le J,D \le 13 $ 初始棋盘棋子分布只用 `J` 和 `D` 这两种字符表示。 ### 样例说明 **样例1：** Justin 拥有 $3$ 种移动的可能性，移动后分别为：（用 `_` 表示空棋子） `_JD`（第一颗向右移），`J_J`（第二颗向右移），`J_D`（第二颗向左移）。 对于情况 1，Justin 败。对于情况 2 和 3，Justin 胜。由于 Justin 的误差常数为 $3$，他会选择所有的情况，故胜率为$\frac{2}{3}$，取 $0.667$。 **样例2：** Justin 拥有 $4$ 种移动的可能性，移动后分别为：（用 `_` 表示空棋子） ``` J_ _J J_ _J DD DD DJ JD ``` 然而，无论 Justin 选择哪种，他都没有可能赢。 之后 Donald 会选择最优的移动。他可以选择以下的方式击败对应的 Justin： ``` D_ _D J_ _J _D D_ _D D_ ``` 故而 Justin 不可能赢。