题目描述

译自 CCO 2019 Day1 T1「Human Error」。

贾斯汀和唐纳德正在玩他们最喜欢的游戏：跳棋。你可能没听说过，不过规则还挺简单的。

棋盘是一个矩形格子，每个格子一开始都放着正好一个玩家的棋子。贾斯汀的棋子用 $\texttt{J}$ 表示，唐纳德的棋子用 $\texttt{D}$ 表示。游戏开始时，每个人棋盘上至少会有一个棋子。

游戏由贾斯汀率先开始。每回合，玩家可以移动一枚自己的棋子，吃掉并移除相邻的一个任意一方的棋子。如果一个棋子 $X$ 在 $Y$ 的上下左右任何一个方向，那么就称 $X$ 和 $Y$ 是相邻的。如果无法进行这样的移动，那么当前玩家就输了。

理想情况下，贾斯汀和唐纳德都是完美逻辑学家，能够针对任何棋盘形势制定最佳策略。那么我们也许会想知道谁会赢。但这并不现实。实际上，在游戏中，贾斯汀和唐纳德都能想出一个相对好的方案；方案的好坏程度取决于他们的失误因子，分别记为 $J$ 和 $D$。

更正式地说，当前玩家的失误因子为 $A$ 时，他会先选择一个提议集合：如果可选的移动步数少于或等于 $A$，那么提议集合就是所有可能的移动；如果可选的移动步数多于 $A$，那么提议集合是他从所有可能移动中挑选出来的 $A$ 个移动组成的子集。然后，玩家会从这个提议集合中随机选择一个移动，每个移动的被选概率相等。

双方在选择提议集合时，都会选择最优的集合（能带来最高获胜概率的集合），并且知道对方也会以同样的方式选择最优的提议集合。

给定初始棋盘状态、贾斯汀的失误因子 $J$ 和唐纳德的失误因子 $D$，贾斯汀赢得跳棋游戏的概率是多少？

输入格式

第一行包含两个空格分隔的正整数 $R, C$。接下来的 $R$ 行包含初始棋盘状态的字符串，每行包含 $C$ 个字符 $\texttt{J}, \texttt{D}$。最后一行包含两个空格分隔的正整数 $J,D$。

输出格式

输出一个浮点数表示贾斯汀获胜的概率，四舍五入到小数点后三位数。

1 3
JJD
3 1

0.667

注意，贾斯汀有 $3$ 种可能的移动方式（下文中 _ 表示空格子）：

• 他向右移动他的第一个棋子，吃掉他的第二个棋子，导致棋盘变成 \texttt{_JD}，从而输掉游戏；
• 他向右移动他的第二个棋子，吃掉唐纳德的棋子并取得胜利，棋盘变成 \texttt{J_J}；
• 或者他向左移动他的第二个棋子，吃掉自己的棋子，但让唐纳德无法移动，从而也取得胜利，棋盘变成 \texttt{J_D}。

显然后两种情况才是最优的——但由于贾斯汀的失误因素为 $3$，所以他选择导致自己输掉的那步的概率是 $1/3$。因此，他获胜的概率是 $2/3$。

2 2
JJ
DD
3 1

0.000

贾斯汀没有获胜的希望。

贾斯汀的第一步有 $4$ 种可能的选择：

J_   _J   J_   _J
DD   DD   DJ   JD

他可以从上述移动中选择任意大小为 $3$ 的子集。

然而，唐纳德总是会选择他最优的移动。无论贾斯汀的第一步是什么，唐纳德都会将棋盘变成以下几种局面之一：

D_   _J   _D   J_
_D   D_   D_   _D

这些局面都会导致贾斯汀输掉游戏。

数据范围与提示

对于 $100\%$ 的数据，$R \times C \leq 13$，$1 \leq J, D \leq 13$。