题目描述

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 3
JJD
3 1

0.667

2 2
JJ
DD
3 1

0.000

提示

限制

$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不可能赢。