题目描述

Codejamom is a mobile game in which monster trainers walk around in the real world to catch monsters. You have an old smartphone with a short battery life, so you need to choose your path carefully to catch as many monsters as possible.

Suppose the Codejamom world is a rectangular grid with $R$ rows and $C$ columns. Rows are numbered from top to bottom, starting from 0; columns are numbered from left to right, starting from 0. You start in the cell in the $R_S$th row and the $C_S$th column. You will take a total of $S$ unit steps; each step must be to a cell sharing an edge (not just a corner) with your current cell.

Whenever you take a step into a cell in which you have not already caught a monster, you will catch the monster in that cell with probability $P$ if the cell has a monster attractor, or $Q$ otherwise. If you do catch the monster in a cell, it goes away, and you cannot catch any more monsters in that cell, even on future visits. If you do not catch the monster in a cell, you may still try to catch the monster on a future visit to that cell. The starting cell is special: you have no chance of catching a monster there before taking your first step.

If you plan your path optimally before making any move, what is the maximum possible expected number of monsters that you will be able to catch?

The battery can only support limited steps, so hurry up!

输入格式

The first line of the input gives 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 in the grid; $R_S$ and $C_S$ are the numbers of the row and column of your starting position, and $S$ is the number of steps you are allowed to take.

The next line contains two decimals $P$ and $Q$, where $P$ is the probability of meeting a monster in cells with a monster attractor, and $Q$ is the probability of meeting a monster in cells without a monster attractor. $P$ and $Q$ are each given to exactly four decimal places.

Each of the next $R$ lines contains contains $C$ space-separated characters; the $j$-th character of the $i$-th line represents the cell at row $i$ and column $j$. Each element is either . (meaning there is no attractor in that cell) or A (meaning there is an attractor in that cell).

输出格式

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the largest possible expected number of monsters that the player can catch in the given amount of steps.

$y$ will be considered correct if $y$ is within an absolute or relative error of $10^{-6}$ of the correct answer.

2
4 4 0 0 5
0.8000 0.2000
. . . .
. . . .
. . A .
. A . A
10 10 9 1 4
0.6121 0.1000
. . A A . . . . . .
A . . . . . . . . .
. . A . . . . A . .
. . . A A . . . . .
. A A A . . . . . A
A . A A . . . . A .
. A . . . . . A . .
. . . . A A . . . .
. . A . . . A . . A
. . . . A . . A . .

Case #1: 1.6000000
Case #2: 1.0495336

提示

In Case #1, one of the best paths 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 will catch is $0.2 + 0.2 + 0.2 + 0.8 + 0.2 = 1.6$. Remember that there is no chance of catching a monster before taking your first step, which is why there are five probabilities in the calculation, not six.

In Case #2, one of the best paths is $(9,1)\to(9,2)\to(8,2)\to(8,3)\to(8,2)$. On this path, the expected number of monsters that you will catch is $0.1 + 0.6121 + 0.1 + 0.23743359 = 1.04953359$. Since we accept results within an absolute or relative error of $10^{-6}$ of the correct answer ($1.04953359$), $1.0495336$ is accepted.

Limits

$1 \le T \le 100$.

$0 \le R_S < R$.

$0 \le C_S < C$.

$0 \le Q < P \le 1$.

Small dataset (Test set 1 - Visible)

$1 \le R \le 10$.

$1 \le C \le 10$.

$0 \le S \le 5$.

Large dataset (Test set 2 - Hidden)

$1 \le R \le 20$.

$1 \le C \le 20$.

$0 \le S \le 9$.