몬스터 경로

Codejamon은 몬스터 조련사들이 몬스터를 잡기 위해 현실 세계를 돌아다니는 모바일 게임이다. 당신에게는 배터리 사용 시간이 짧은 오래된 스마트폰이 있으므로, 가능한 한 많은 몬스터를 잡기 위해 경로를 신중하게 선택해야 한다.

Codejamon 세계가 R개의 행과 C개의 열로 이루어진 직사각형 격자라고 하자. 행은 위에서 아래로 0부터 번호가 매겨지고, 열은 왼쪽에서 오른쪽으로 0부터 번호가 매겨진다. 당신은 $R_{s}$번째 행과 $C_{s}$번째 열에 있는 칸에서 시작한다. 총 S번의 단위 이동을 하며, 각 이동에서는 현재 칸과 변을 공유하는 칸으로 이동해야 한다(모서리만 공유하는 칸은 안 된다).

아직 몬스터를 잡지 않은 칸으로 이동할 때마다, 그 칸에 몬스터 유인기가 있으면 확률 P로, 그렇지 않으면 확률 Q로 그 칸의 몬스터를 잡는다. 한 칸에서 몬스터를 잡으면 그 몬스터는 사라지며, 이후에 다시 방문하더라도 그 칸에서는 더 이상 몬스터를 잡을 수 없다. 한 칸에서 몬스터를 잡지 못했다면, 이후에 그 칸을 다시 방문하여 몬스터 잡기를 시도할 수 있다. 시작 칸에는 특별한 규칙이 적용된다. 첫 이동을 하기 전에는 그곳에서 몬스터를 잡을 가능성이 없다.

어떤 이동도 하기 전에 경로를 최적으로 계획한다면, 잡을 수 있는 몬스터 수의 가능한 최댓값의 기댓값은 얼마인가?

배터리로는 제한된 횟수만큼만 이동할 수 있으므로 서둘러라!

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 0 ≤ $R_{s}$ < R. 0 ≤ $C_{s}$ < C. 0 ≤ Q < P ≤ 1.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ R ≤ 10. 1 ≤ C ≤ 10. 0 ≤ S ≤ 5.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ R ≤ 20. 1 ≤ C ≤ 20. 0 ≤ S ≤ 9.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 다섯 정수 R, C, $R_{s}$, $C_{s}$, S가 있는 한 줄로 시작한다. R과 C는 격자의 행과 열의 수이고, $R_{s}$와 $C_{s}$는 시작 위치의 행 번호와 열 번호이며, S는 허용된 이동 횟수이다.

다음 줄에는 두 소수 P와 Q가 주어진다. P는 몬스터 유인기가 있는 칸에서 몬스터를 만날 확률이고, Q는 몬스터 유인기가 없는 칸에서 몬스터를 만날 확률이다. P와 Q는 각각 정확히 소수점 이하 네 자리까지 주어진다.

이어지는 R개의 각 줄에는 공백으로 구분된 C개의 문자가 포함되어 포함된다. i번째 줄의 j번째 문자는 i행 j열의 칸을 나타낸다. 각 원소는 .(그 칸에 유인기가 없다는 뜻) 또는 A(그 칸에 유인기가 있다는 뜻) 중 하나이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 주어진 이동 횟수 동안 플레이어가 잡을 수 있는 몬스터 수의 가능한 최댓값의 기댓값이다.

y은 y이 정답과의 절대 오차 또는 상대 오차가 10^{-6} 이내이면 정답으로 간주된다. 이것이 의미하는 바와 허용되는 실수 형식에 대한 설명은 FAQ을 참고하라.

케이스 #1에서 최적 경로 중 하나는 (0,0)->(0,1)->(0,2)->(1,2)->(2,2)->(2,3)이다. 이 경로에서 잡게 될 몬스터 수의 기댓값은 0.2 + 0.2 + 0.2 + 0.8 + 0.2 = 1.6이다. 첫 이동을 하기 전에는 몬스터를 잡을 가능성이 없다는 점을 기억하라. 이 때문에 계산에 확률이 여섯 개가 아니라 다섯 개 있다.

케이스 #2에서 최적 경로 중 하나는 (9,1)->(9,2)->(8,2)->(8,3)->(8,2)이다. 이 경로에서 잡게 될 몬스터 수의 기댓값은 0.1 + 0.6121 + 0.1 + 0.23743359 = 1.04953359이다. 정답과의 절대 오차 또는 상대 오차가 10^{-6} 이내인 결과를 허용하므로(정답은 1.04953359), 1.0495336도 허용된다.