LOOPS

Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 125536/65536 K (Java/Others)
Total Submission(s): 2734 Accepted Submission(s): 1132


Problem Description Akemi Homura is a Mahou Shoujo (Puella Magi/Magical Girl).

Homura wants to help her friend Madoka save the world. But because of the plot of the Boss Incubator, she is trapped in a labyrinth called LOOPS.

The planform of the LOOPS is a rectangle of R*C grids. There is a portal in each grid except the exit grid. It costs Homura 2 magic power to use a portal once. The portal in a grid G(r, c) will send Homura to the grid below G (grid(r+1, c)), the grid on the right of G (grid(r, c+1)), or even G itself at respective probability (How evil the Boss Incubator is)!
At the beginning Homura is in the tZ喎?/kf/ware/vc/" target="_blank" class="keylink">vcCBsZWZ0IGNvcm5lciBvZiB0aGUgTE9PUFMgKCgxLCAxKSksIGFuZCB0aGUgZXhpdCBvZiB0aGUgbGFieXJpbnRoIGlzIGluIHRoZSBib3R0b20gcmlnaHQgY29ybmVyICgoUiwgQykpLiBHaXZlbiB0aGUgcHJvYmFiaWxpdHkgb2YgdHJhbnNtaXNzaW9ucyBvZiBlYWNoIHBvcnRhbCwgeW91ciB0YXNrIGlzIGhlbHAgcG9vciBIb211cmEgY2FsY3VsYXRlIHRoZSBFWFBFQ1QgbWFnaWMgcG93ZXIKIHNoZSBuZWVkIHRvIGVzY2FwZSBmcm9tIHRoZSBMT09QUy48YnI+Cjxicj4KPGJyPgo8YnI+Cjxicj4KCiAKPGJyPgpJbnB1dApUaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgUiBhbmQgQyAoMiA8PSBSLCBDIDw9IDEwMDApLjxicj4KPGJyPgpUaGUgZm9sbG93aW5nIFIgbGluZXMsIGVhY2ggY29udGFpbnMgQyozIHJlYWwgbnVtYmVycywgYXQgMiBkZWNpbWFsIHBsYWNlcy4gRXZlcnkgdGhyZWUgbnVtYmVycyBtYWtlIGEgZ3JvdXAuIFRoZSBmaXJzdCwgc2Vjb25kIGFuZCB0aGlyZCBudW1iZXIgb2YgdGhlIGN0aCBncm91cCBvZiBsaW5lIHIgcmVwcmVzZW50IHRoZSBwcm9iYWJpbGl0eSBvZiB0cmFuc3BvcnRhdGlvbiB0byBncmlkIChyLCBjKSwgZ3JpZCAociwgYyYjNDM7MSksIGdyaWQgKHImIzQzOzEsCiBjKSBvZiB0aGUgcG9ydGFsIGluIGdyaWQgKHIsIGMpIHJlc3BlY3RpdmVseS4gVHdvIGdyb3VwcyBvZiBudW1iZXJzIGFyZSBzZXBhcmF0ZWQgYnkgNCBzcGFjZXMuPGJyPgo8YnI+Ckl0IGlzIGVuc3VyZWQgdGhhdCB0aGUgc3VtIG9mIHRocmVlIG51bWJlcnMgaW4gZWFjaCBncm91cCBpcyAxLCBhbmQgdGhlIHNlY29uZCBudW1iZXJzIG9mIHRoZSByaWdodG1vc3QgZ3JvdXBzIGFyZSAwIChhcyB0aGVyZSBhcmUgbm8gZ3JpZHMgb24gdGhlIHJpZ2h0IG9mIHRoZW0pIHdoaWxlIHRoZSB0aGlyZCBudW1iZXJzIG9mIHRoZSBkb3dubW9zdCBncm91cHMgYXJlIDAgKGFzIHRoZXJlIGFyZSBubyBncmlkcyBiZWxvdyB0aGVtKS48YnI+Cjxicj4KWW91IG1heSBpZ25vcmUgdGhlIGxhc3QgdGhyZWUgbnVtYmVycyBvZiB0aGUgaW5wdXQgZGF0YS4gVGhleSBhcmUgcHJpbnRlZCBqdXN0IGZvciBsb29raW5nIG5lYXQuPGJyPgo8YnI+ClRoZSBhbnN3ZXIgaXMgZW5zdXJlZCBubyBncmVhdGVyIHRoYW4gMTAwMDAwMC48YnI+Cjxicj4KVGVybWluYWwgYXQgRU9GPGJyPgo8YnI+Cjxicj4KCiAKPGJyPgpPdXRwdXQKQSByZWFsIG51bWJlciBhdCAzIGRlY2ltYWwgcGxhY2VzIChyb3VuZCB0byksIHJlcHJlc2VudGluZyB0aGUgZXhwZWN0IG1hZ2ljIHBvd2VyIEhvbXVyYSBuZWVkIHRvIGVzY2FwZSBmcm9tIHRoZSBMT09QUy48YnI+Cjxicj4KCiAKPGJyPgpTYW1wbGUgSW5wdXQKCjxwcmUgY2xhc3M9"brush:java;">2 2 0.00 0.50 0.50 0.50 0.00 0.50 0.50 0.50 0.00 1.00 0.00 0.00
Sample Output

6.000

#include
#include
#include
#include
using namespace std;

#define M  1005
#define exp  1e-5
double dp[M][M];
double p1[M][M];
double p2[M][M];
double p3[M][M];

int main(){
    int n,m;
    while(cin>>n>>m){
        int i,j;
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                cin>>p1[i][j]>>p2[i][j]>>p3[i][j];

        dp[n][m]=0;
        for(i=n;i>=1;i--)
        for(j=m;j>=1;j--){
            if(i==n && j==m)   continue;
            if(fabs(1-p1[i][j])