Description

Justin and Donald are playing a game: checkers. You may not have heard of it, but the rules are very simple.

The board is a rectangular grid. At the beginning, each cell contains exactly one piece, and each player has at least one piece on the board. Justin’s pieces are marked J, and Donald’s are marked D.

Justin moves first. In one move, the player may move one of their own pieces and capture one adjacent piece (not necessarily the opponent’s), then it becomes the other player’s turn. If the current player cannot make such a move, then this player loses.

Pieces $A$ and $B$ are adjacent if and only if $A$ is exactly one cell above, below, left, or right of $B$.

In an ideal world, both players are perfect logicians and can know the best strategy for every board position. However, this is not realistic. In fact, while playing, they only choose relatively good moves. How good it is depends on Justin’s and Donald’s error constants, which are $J$ and $D$, respectively.

Formally, a player with error constant $A$ will select a set of plans consisting of $A$ moves from all possible moves. If the number of all possible moves $P \le A$, then the plan set contains only these $P$ moves. Then, the player randomly (with equal probability) picks one move from the set and makes that move.

When choosing which moves form the set, both players always choose the optimal set, and they also know that the opponent will choose the optimal set.

What is the probability that Justin wins?

Input Format

The first line contains two positive integers $R C$ (separated by a space).

Then there are $R$ lines, each containing $C$ characters, representing the initial distribution of pieces on the board (see the description for meanings).

Then one line contains two positive integers $J D$ (separated by a space), with the meanings described above.

Output Format

Output one line with a floating-point number rounded to 3 decimal places, representing the probability that Justin wins.

1 3
JJD
3 1

0.667

2 2
JJ
DD
3 1

0.000

Hint

Constraints

$1 \le R \times C \le 13$

$1 \le J,D \le 13$

The initial board distribution uses only the two characters J and D.

Sample Explanation

Sample 1:

Justin has 3 possible moves, and the resulting boards are (use _ to represent an empty cell).

_JD (move the first piece to the right), J_J (move the second piece to the right), J_D (move the second piece to the left).

For case 1, Justin loses. For cases 2 and 3, Justin wins. Since Justin’s error constant is 3, he will choose all cases, so the win rate is $\frac{2}{3}$, which is $0.667$.

Sample 2:

Justin has 4 possible moves, and the resulting boards are (use _ to represent an empty cell).

J_ _J J_ _J
DD DD DJ JD

However, no matter which one Justin chooses, he has no way to win.

Then Donald will choose the optimal move. He can choose the following moves to defeat the corresponding Justin moves:

D_ _D J_ _J
_D D_ _D D_

Therefore, Justin cannot win.

Translated by ChatGPT 5