Optimized Checkers Game with Limited Error Choices

Justin and Donald are playing a game called Checkers. Initially, the board is a rectangular grid where every cell contains exactly one piece. Each player has at least one piece: Justin’s pieces are marked with J and Donald’s pieces with D.

Justin moves first. In a single move, the current player selects one of his own pieces and moves it to an adjacent cell (up, down, left, or right) that is occupied by another piece (which may belong to either player), capturing that piece. The cell from which the moving piece came becomes empty, and the target cell is replaced by the moving player’s piece. After the move, the turn passes to the opponent. If the current player has no legal move, he loses.

Neither player is perfectly rational; instead, each has an error constant: \(J\) for Justin and \(D\) for Donald. Formally, when it is a player’s turn with error constant \(A\), let \(P\) be the total number of legal moves. If \(P \le A\), then all moves are considered. Otherwise, the player only considers the best \(A\) moves (i.e. the moves that maximize that player’s winning probability, assuming both players continue to play optimally under their error constraints) and then selects one uniformly at random from these \(A\) moves.

Given the initial board configuration and the error constants for both players, compute the probability that Justin wins the game. If a move leads to a state where the probability of the opponent winning is \(x\), then the value of that move is \(1-x\). Both players know that their opponent is using the same strategy.

inputFormat

The first line contains two integers \(r\) and \(c\) \((1 \le r, c \le 4)\), representing the number of rows and columns of the board.

The second line contains two integers \(J\) and \(D\) \((1 \le J, D \le 10)\), representing the error constants for Justin and Donald respectively.

The following \(r\) lines each contain a string of length \(c\) composed only of the characters J and D, indicating the initial board configuration. It is guaranteed that both players have at least one piece on the board.

outputFormat

Output a single real number: the probability that Justin wins the game. Answers with an absolute or relative error of at most \(10^{-6}\) will be accepted.

sample

1 2
1 1
JD

1.000000