Veenus on Adventure Trip

Problem code: ADVTRIP

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 non-planned 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.

http://picasaweb.google.com/anvaysrivastava/Alkhawarizm?authkey=Gv1sRgCKiltti18crPxwE#5522750285503722514

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 (row-major) 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 (i-1,j) k
Set 4 West: Probability of moving from p (i,j) k to p (i-1,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
Date Added: 28-09-2010
Time Limit: 3.5 sec
Source Limit: 50000 Bytes
Languages: C, C99 strict, CLOJ, CPP 4.0.0-8, CPP 4.3.2, F#, GO, PERL6, PYTH 3.1.2, TEXT


Comments

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

HELP

Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:

 

  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • If you are still having problems, see a sample solution here.

CodeChef is a global programming communityCodeChef hosts online programming competitions