Monster Path (Small)

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

The Codejamon world is a rectangular 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 in row $R_s$ and column $C_s$, and you take exactly $S$ unit steps. One step moves you to a cell that shares an edge with your current cell. A cell that only shares a corner is not reachable in one step.

Whenever you step into a cell where you have not caught a monster yet, you catch the monster in that cell with probability $P$ if the cell has a monster attractor, and with probability $Q$ if it does not. Once you catch the monster in a cell, it goes away, and later visits to that cell give you nothing. If you fail, you try again on every later visit to that cell. The starting cell is an exception. You have no chance of catching a monster there before your first step.

You plan the whole path before you move. Find the largest possible expected number of monsters that you catch.

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

Each test case starts with a line of five integers $R$, $C$, $R_s$, $C_s$ and $S$. $R$ and $C$ are the numbers of rows and columns of the grid, ($R_s$, $C_s$) is 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 a monster in a cell with an attractor, and $Q$ is the probability in a cell without one. Both are given with exactly four digits after the decimal point.

Each of the next $R$ lines contains $C$ characters separated by spaces. The $j$-th character of the $i$-th line describes the cell in row $i$ and column $j$. It is . if the cell has no attractor, and A if it has one.

Limits

• $1 \le T \le 100$
• $1 \le R \le 10$
• $1 \le C \le 10$
• $0 \le R_s < R$
• $0 \le C_s < C$
• $0 \le Q < P \le 1$
• $0 \le S \le 5$
• If $R = 1$ and $C = 1$, then $S = 0$.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting at 1 and $y$ is the largest expected number of monsters you can catch within the given number of steps.

Print $y$ with exactly seven digits after the decimal point, rounded at the eighth decimal digit. A digit 5 in the eighth decimal place rounds the seventh place up. Print a zero answer as 0.0000000.

In the first test case of the example, one optimal path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (2,3). The expected number of monsters caught on it is 0.2 + 0.2 + 0.2 + 0.8 + 0.2 = 1.6. There is no chance to catch a monster before the first step, so five probabilities are added, not six.

In the second test case, one optimal path is (9,1) -> (9,2) -> (8,2) -> (8,3) -> (8,2). The expected value is 0.1 + 0.6121 + 0.1 + 0.23743359 = 1.04953359, which prints as 1.0495336. The term 0.23743359 for the second entry into (8,2) is 0.3879, the probability that the first attempt failed, times 0.6121.