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??http://www.2cto.com/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])


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：hdu4311 曼哈顿距离	下一篇：UVA 10341 (二分查找+精度)

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: