Monster Path (Large)

Codejamon is a mobile game in which monster trainers walk around the real world to catch monsters. Your smartphone is old and its battery runs out quickly, so you have to choose your path carefully to catch as many monsters as possible.

The Codejamon world is a grid with $R$ rows and $C$ columns. Rows are numbered from top to bottom starting at $0$, and columns are numbered from left to right starting at $0$. You start in the cell at row $R_s$ and column $C_s$, and you take exactly $S$ unit steps. Each step must go to a cell that shares an edge with your current cell. A cell that shares only a corner does not count.

Whenever you step into a cell in which you have not yet caught the monster, you try to catch it. You succeed with probability $P$ if the cell has a monster attractor, and with probability $Q$ otherwise. A monster that you catch goes away, so you cannot catch another monster in that cell, even on later visits. If you fail, you can try again the next time you step into that cell. The starting cell is special: you have no chance of catching its monster before your first step.

You plan your path optimally before you make any move. Find the maximum possible expected number of monsters that you catch.

If $R = 1$ and $C = 1$, there is no cell to step into. In that case the expected number is $0$, even when $S$ is $1$ or more.

The first line contains the number of test cases $T$. $T$ test cases follow.

Each test case starts with a line of five space-separated integers $R$, $C$, $R_s$, $C_s$, and $S$. $R$ and $C$ are the numbers of rows and columns in the grid, $R_s$ and $C_s$ are the row and column of your starting cell, and $S$ is the number of steps you take.

The next line contains two decimals $P$ and $Q$. $P$ is the probability of catching the monster in a cell with a monster attractor, and $Q$ is the probability of catching the monster in a cell without one. Each value is given to exactly four decimal places.

Each of the next $R$ lines contains $C$ space-separated characters. The $j$-th character of the $i$-th line describes the cell at row $i$ and column $j$. Each character is either ., meaning the cell has no attractor, or A, meaning the cell has an attractor.

Limits

• $1 \le T \le 100$
• $1 \le R \le 20$
• $1 \le C \le 20$
• $0 \le R_s < R$
• $0 \le C_s < C$
• $0 \le Q < P \le 1$
• $0 \le S \le 9$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from $1$ and $y$ is the maximum possible expected number of monsters that you catch.

Print $y$ rounded half up to exactly seven digits after the decimal point. Print all seven digits even when the value is an integer, as in 2.0000000. No input has an answer that lies exactly on a rounding boundary.

In the first test case of the first example, one optimal path is $(0,0) \to (0,1) \to (0,2) \to (1,2) \to (2,2) \to (2,3)$. On this path, the expected number of monsters that you catch is $0.2 + 0.2 + 0.2 + 0.8 + 0.2 = 1.6$. You have no chance of catching a monster before your first step, which is why the sum has five probabilities, not six.

In the second test case of the same example, one optimal path is $(9,1) \to (9,2) \to (8,2) \to (8,3) \to (8,2)$. The expected number is $0.1 + 0.6121 + 0.1 + 0.23743359 = 1.04953359$, which rounds to $1.0495336$ in the required format. The last term, $0.23743359$, is the probability $1 - 0.6121$ that the monster in $(8,2)$ is still there on your second visit, multiplied by the catch probability $0.6121$.