{"id":109,"date":"2010-09-02T08:26:25","date_gmt":"2010-09-02T00:26:25","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=109"},"modified":"2012-03-03T08:26:44","modified_gmt":"2012-03-03T00:26:44","slug":"f-maze-stretching","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/f-maze-stretching\/","title":{"rendered":"F. Maze Stretching"},"content":{"rendered":"<p><!--more--><\/p>\n<h3>Analyse :<\/h3>\n<p>  \u6211\u4e4b\u524d\u60f3\u7684\u590d\u6742\u4e86\u4e9b\uff0c\u6bd4\u5982\u8bf4\u5982\u679c\u67d0\u4e00\u8f6e\u5728\u641c\u7d22\u7684\u65f6\u5019\u5982\u679c\u6cbf\u7740\u4e00\u4e2a\u65b9\u5411\u79fb\u52a8\u6b21\u6570\u5df2\u7ecf\u8fbe\u5230\u4e86\u6700\u5c0f\u503c\uff0c\u90a3\u4e48\u7ee7\u7eed\u5c06\u8fd9\u4e2a\u65b9\u5411\u7684\u6743\u503c\u589e\u52a0\u5927\u7684\u8bdd\uff0c\u8fd9\u4e2a\u503c\u53ef\u4ee5\u76f4\u63a5\u4e58\u51fa\u6765\uff0c\u4f46\u662f\u6700\u540e\u7684\u4ee3\u7801\u53ea\u662f\u7b80\u5355\u7684\u4e8c\u5206\u7b54\u6848\u52a0BFS\u3002<\/p>\n<p> \u53e6\u4e00\u4e2a\u9700\u8981\u7559\u610f\u7684\u662f\u7cbe\u5ea6\u63a7\u5236\u3002\u3002\u3002\u6211\u5e94\u8be5\u662f\u6ca1\u6709\u5199\u9519\u7684\u5427\u3002<\/p>\n<pre lang=\"cpp\">\r\n\/*\r\n    Author : xiaodao\r\n    Series : SERPC 2009 \r\n    Prob.  : F. Maze Stretching\t\r\n*\/\r\n#include <iostream>\r\n#include <cstdio>\r\n#include <cstring>\r\n#include <string>\r\n#include <queue>\r\n\r\nusing namespace std;\r\nconst int dx[4] = {0, 0, 1, -1};\r\nconst int dy[4] = {1, -1, 0, 0};\r\nconst double INF = 1e10, e = 0.0000001;\r\nconst int N = 100;\r\n\r\nstruct po{\r\n    int x, y;\r\n    friend bool operator ==(po a, po b){\r\n        return a.x==b.x && a.y==b.y;\r\n    }\r\n};\r\nstruct re{\r\n    po p; double k;\r\n    friend bool operator <(re a, re b){\r\n        return a.k>b.k;\r\n    }\r\n};\r\n\r\nchar maze[N+3][N+3]; bool hash[N+3][N+3];\r\ndouble L, ans; po st, ed; re u, v;\r\nint n, m;\r\n\r\n\r\n\r\n\r\ndouble bfs(double w){\r\n    memset(hash, false, sizeof(hash));\r\n    priority_queue<re> Q;\r\n    u.p = st; u.k = 0; Q.push(u);\r\n\r\n    while (!Q.empty()){\r\n        u = Q.top(); Q.pop(); if (hash[u.p.x][u.p.y]) continue;\r\n        if (u.p == ed) return u.k;\r\n\r\n        hash[u.p.x][u.p.y] = true;\r\n        for (int i=0;i<2;i++){\r\n            v.p.x = u.p.x + dx[i]; v.p.y = u.p.y + dy[i];\r\n            if (hash[v.p.x][v.p.y] || maze[v.p.x][v.p.y]=='#') continue;\r\n            v.k = u.k + 1;\r\n            Q.push(v);\r\n        }\r\n        for (int i=2;i<4;i++){\r\n            v.p.x = u.p.x + dx[i]; v.p.y = u.p.y + dy[i];\r\n            if (hash[v.p.x][v.p.y] || maze[v.p.x][v.p.y]=='#') continue;\r\n            v.k = u.k + w;\r\n            Q.push(v);\r\n        }\r\n    }\r\n    return INF;\r\n}\r\n\r\nvoid solve(){\r\n    double l = 0, r = 10, m;\r\n    while (r-l>e){\r\n        m = (l + r)\/2;\r\n        if (bfs(m)<=L) l = m;\r\n        else r = m;\r\n    }\r\n    ans = l;\r\n}\r\n\r\nvoid init(){\r\n    scanf(\"%lf%d\", &#038;L, &#038;n);\r\n    string s; cin.get(); getline(cin, s); m = s.size();\r\n    memset(maze, '#', sizeof(maze));\r\n    for (int j=0;j<m;j++)\r\n        maze[1][j+1] = s[j];\r\n\r\n    for (int i=2;i<=n;i++){\r\n        getline(cin, s);\r\n        for (int j=0;j<m;j++)\r\n            maze[i][j+1] = s[j];\r\n    }\r\n\r\n    for (int i=1;i<=n;i++)\r\n        for (int j=1;j<=m;j++){\r\n            if (maze[i][j]=='S') st.x = i, st.y = j;\r\n            else if (maze[i][j]=='E') ed.x = i, ed.y = j;\r\n        }\r\n}\r\n\r\nvoid patch(){\r\n    for (int i=1;i<=n;i++){\r\n        for (int j=1;j<=m;j++)\r\n            cout << maze[i][j];\r\n        cout << endl;\r\n    }\r\n}\r\n\r\n\r\nint main(){\r\n    freopen(\"F.in\", \"r\", stdin);\r\n    freopen(\"F.out\", \"w\", stdout);\r\n    int T, i; scanf(\"%d\", &#038;T);\r\n    for (int i=1;i<=T;i++){\r\n        init(); solve();\r\n        printf(\"Case #%d: %.3lf%%\\n\", i, ans*100);\r\n    }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-109","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-1L","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/109","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=109"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/109\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=109"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=109"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=109"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}