Veenus on Adventure Trip

All submissions for this problem are available.
Veenus is a big fan of adventure trips. One day she heard about a distant nation called "Pandora". As nonplanned trips sound more adventurous, she packed her bag with essentials and started her journey. She was completely unaware of the transit tax that one has to pay when one enters a nation (she has to pay transit tax to revisit (1,1) during her trip). The transit tax is valid for a single entry. Also she didn't bring any maps with her so she can go from one nation to another in a random manner (you can assume that each move is independent of any previous moves that she has taken). She can revisit already visited nations. Considering the random moves, calculate the expected amount of transit tax paid by her.
For the matter of simplicity, assume that the nation is a rectangle of size MxN with MN nations. Each nation has 4 neighboring other nations (except ones on the border). Veenus starts with nation (1, 1) and has to reach nation (M, N) where Pandora is located to complete her adventure trip. Also to make the problem even simpler, let's say each nation charges unit money for transit which is common currency for the entire nations.
Input
The input start with integer M, N (1 <= M, N<= 40) on each line. Then followed by 4 set of M x N numbers (rowmajor) where each of 4 set represent one of the directions
Set 1 North: Probability of moving from p_{ (i,j) } ^{k} to p_{ (i+1,j) } ^{k}
Set 2 East: Probability of moving from p_{ (i,j) } ^{k} to p_{ (i,j+1) } ^{k}
Set 3 South: Probability of moving from p_{ (i,j) } ^{k} to p_{ (i1,j) } ^{k}
Set 4 West: Probability of moving from p_{ (i,j) } ^{k} to p_{ (i1,j) } ^{k}
Input is terminated when M = 0 and N = 0.
Output
Expected transit money that will be required by Veenus to reach her destination nation(M, N). Expected money should be printed up to 8 places after decimal.
Examples
Example 1 Input 2 4 0.690000 0.150000 0.900000 0.920000 0.000000 0.000000 0.000000 0.000000 0.310000 0.650000 0.070000 0.000000 0.940000 0.040000 0.140000 0.000000 0.000000 0.000000 0.000000 0.000000 0.060000 0.570000 0.050000 0.000000 0.000000 0.200000 0.030000 0.080000 0.000000 0.390000 0.810000 0.000000 0 0 Example 1 Output 37.07916764 Example 2 Input 1 3 0.000000 0.000000 0.000000 1.000000 0.370000 0.000000 0.000000 0.000000 0.000000 0.000000 0.630000 0.000000 0 0 Example 2 Output 5.40540541 Example 3 Input 6 4 0.730000 0.270000 0.380000 0.930000 0.250000 0.030000 0.630000 0.930000 0.060000 0.100000 0.180000 0.500000 0.750000 0.980000 0.320000 0.760000 0.100000 0.380000 0.290000 0.950000 0.000000 0.000000 0.000000 0.000000 0.270000 0.400000 0.370000 0.000000 0.720000 0.150000 0.240000 0.000000 0.650000 0.650000 0.460000 0.000000 0.230000 0.020000 0.160000 0.000000 0.170000 0.270000 0.640000 0.000000 0.250000 0.500000 0.790000 0.000000 0.000000 0.000000 0.000000 0.000000 0.030000 0.400000 0.040000 0.010000 0.290000 0.180000 0.180000 0.010000 0.020000 0.000000 0.180000 0.130000 0.730000 0.240000 0.010000 0.010000 0.750000 0.040000 0.100000 0.000000 0.000000 0.330000 0.250000 0.070000 0.000000 0.420000 0.090000 0.060000 0.000000 0.070000 0.180000 0.490000 0.000000 0.000000 0.340000 0.110000 0.000000 0.110000 0.060000 0.040000 0.000000 0.460000 0.110000 0.000000 0 0 Example 3 Output 20.07213979
Author:  divij 
Tags  divij 
Date Added:  28092010 
Time Limit:  0.38 sec 
Source Limit:  50000 Bytes 
Languages:  C, C99 strict, CLOJ, COB, CPP 4.3.2, CPP 6.3, CPP14, FS, GO, kotlin, NODEJS, PERL6, PYPY, PYTH 3.5, rust, SCM chicken, swift, TEXT 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 