Glorious Gamblers
Back in 2012 when Digo and Tourist were training for their CIA Assignments, they became good friends. Digo was a skeptical fellow and believed that the world would end that year. Tourist however believed all this did not make any sense. After countless arguments leading to no conclusion, Digo and Tourist finally decided to place a bet on it and move on.
It is 2014 and they meet again on their first assignments. Quite evidently, Digo was proved wrong, and it's time for him to pay back the bet. Both Digo and Tourist being good programmers, they decided to have some fun with the bet. The money that Digo needs to pay Tourist can be expressed in the form of a payoff matrix for Digo. The payoff matrix A[][] is an M*N matrix where every element is a positive integer.
They place a ring on the cell (1,1); and the game ends when the ring wounds up on the cell (M,N). When the ring is on the cell (i,j), they toss a fair coin. If it is a heads, it is Digo's turn to move and if it's a tails it is Tourist's turn. In one turn, a person can move the ring from cell (i,j) to either one cell east, one cell south, or one cell south-east. The ring cannot be moved outside the bounds of the payoff matrix.
The money that Digo need to pay Tourist is the sum of the elements that lie on the path traversed by the ring. Both being logical fellows, Digo would want to minimize the overall money that he needs to pay, while Tourist would want to maximize it.
Help Digo find out the expected money that he would owe Digo at the end of the game. (correct to exactly 6 decimal places)
NOTE: LARGE INPUT FILES. USE FASTER I/O.
Input Format:
The first line contains T, the number of test cases.
For every test case, the first line contains two integers M,N; the dimensions of the matrix.
The next M lines contain N integers each, such that the jth element on the ith line is the element A[i][j] in the payoff matrix.
Output Format:
For every test case, output exactly one result, which is the expected value of the money that Digo would own Tourist at the end of the game (correct to exactly 6 decimal places).
Constraints:
1<= T <=10
2 <= M,N <= 500
0 <= A[i][j] <=10^6
Sample Input
1
2 3
1 2 2
3 5 1
Sample Output
8.250000
It is 2014 and they meet again on their first assignments. Quite evidently, Digo was proved wrong, and it's time for him to pay back the bet. Both Digo and Tourist being good programmers, they decided to have some fun with the bet. The money that Digo needs to pay Tourist can be expressed in the form of a payoff matrix for Digo. The payoff matrix A[][] is an M*N matrix where every element is a positive integer.
They place a ring on the cell (1,1); and the game ends when the ring wounds up on the cell (M,N). When the ring is on the cell (i,j), they toss a fair coin. If it is a heads, it is Digo's turn to move and if it's a tails it is Tourist's turn. In one turn, a person can move the ring from cell (i,j) to either one cell east, one cell south, or one cell south-east. The ring cannot be moved outside the bounds of the payoff matrix.
The money that Digo need to pay Tourist is the sum of the elements that lie on the path traversed by the ring. Both being logical fellows, Digo would want to minimize the overall money that he needs to pay, while Tourist would want to maximize it.
Help Digo find out the expected money that he would owe Digo at the end of the game. (correct to exactly 6 decimal places)
NOTE: LARGE INPUT FILES. USE FASTER I/O.
Input Format:
The first line contains T, the number of test cases.
For every test case, the first line contains two integers M,N; the dimensions of the matrix.
The next M lines contain N integers each, such that the jth element on the ith line is the element A[i][j] in the payoff matrix.
Output Format:
For every test case, output exactly one result, which is the expected value of the money that Digo would own Tourist at the end of the game (correct to exactly 6 decimal places).
Constraints:
1<= T <=10
2 <= M,N <= 500
0 <= A[i][j] <=10^6
Sample Input
1
2 3
1 2 2
3 5 1
Sample Output
8.250000