{"id":139,"date":"2010-08-04T08:41:45","date_gmt":"2010-08-04T00:41:45","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=139"},"modified":"2012-03-03T19:36:14","modified_gmt":"2012-03-03T11:36:14","slug":"%e5%85%ab%e6%95%b0%e7%a0%81%e9%97%ae%e9%a2%98%e7%9a%84%e7%a0%94%e4%b9%a0%e7%ac%94%e8%ae%b0%e3%80%82","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/%e5%85%ab%e6%95%b0%e7%a0%81%e9%97%ae%e9%a2%98%e7%9a%84%e7%a0%94%e4%b9%a0%e7%ac%94%e8%ae%b0%e3%80%82\/","title":{"rendered":"\u516b\u6570\u7801\u95ee\u9898\u7684\u7814\u4e60\u7b14\u8bb0\u3002"},"content":{"rendered":"<p>\u5176\u5b9e&#8230;\u73b0\u5728&#8230;\u552f\u4e00\u80fd\u6ee1\u8db3\u6211\u7684&#8230; \u5c31\u53ea\u6709\u7528 Astar \u628a\u5b83\u89e3\u51fa\u6765\u4e86\u3002\u3002\u3002<\/p>\n<pre lang=\"cpp\" file=\"bfs.cpp\">\r\n#include <iostream>\r\nusing namespace std;\r\nconst int F[9] = {1,1,2,6,24,120,720,5040,40320};\r\nint queue[362880], dist[362880]; bool hash[362880];\r\nint head, tail, goal;\r\nint a[9], b[2]; bool c[9];\r\n\r\n\r\nint cantor(){\r\n    int x = 0, t, i, j;\r\n    for (i=0;i<9;i++){\r\n        for (j=i+1,t=0;j<9;j++)\r\n            if (a[i]>a[j]) t++;\r\n        x = x * (9-i)  + t;\r\n    }\r\n    return x;\r\n}\r\nvoid recover(int x){\r\n    memset(c, false, sizeof(c));\r\n    memset(a, 0, sizeof(a));\r\n    int t, i;\r\n    for (i=0;i<9;i++){\r\n        while (c[a[i]]) a[i]++;\r\n        while (x >= F[8-i]){\r\n            x -= F[8-i]; a[i]++;\r\n            while (c[a[i]]) a[i]++;\r\n        }\r\n        c[a[i]] = true;\r\n    }\r\n}\r\nint stat(){\r\n    int  inversion_pair = 0;\r\n    for (int i=0;i<8;i++){\r\n        if (a[i]==0) continue;\r\n        for (int j=i+1;j<9;j++){\r\n            if (a[j]==0) continue;\r\n            if (a[i]>a[j]) inversion_pair++;\r\n        }\r\n    }\r\n    return inversion_pair;\r\n}\r\n\r\n\r\n\r\n\r\nvoid init(){\r\n\r\n    int i, j, t;\r\n\r\n    for (i=0;i<9;i++) cin >> a[i];\r\n    queue[0] = cantor(); b[0] = stat();\r\n\r\n    for (i=0;i<9;i++) cin >> a[i];\r\n    goal = cantor(); b[1] = stat();\r\n}\r\n\r\nbool operate(int x, int y){\r\n    swap(a[x], a[y]); queue[tail] = cantor(); swap(a[x], a[y]);\r\n\r\n    if (hash[queue[tail]]) return false;\r\n    dist[tail] = dist[head] + 1;\r\n    if (queue[tail]==goal){\r\n        cout << dist[tail] << endl;\r\n        return true;\r\n    }\r\n\r\n    hash[queue[tail++]] = true;\r\n    return false;\r\n}\r\n\r\nvoid bfs(){\r\n    if (queue[0] == goal) {cout << 0 << endl; return;}\r\n    if (b[0]%2!=b[1]%2) {cout << -1 << endl; return;}\r\n    dist[0] = 0; head = 0; tail = 1;\r\n    memset(hash, false, sizeof(hash));\r\n    hash[queue[0]] = true;\r\n\r\n    int p;\r\n    while (true){\r\n        recover(queue[head]);\r\n\r\n        for (p=0;a[p]!=0;p++);\r\n        if (p > 2) if (operate(p, p-3)) return;\r\n        if (p < 6) if (operate(p, p+3)) return;\r\n        if (p % 3) if (operate(p, p-1)) return;\r\n        if ((p+1) % 3) if (operate(p, p+1)) return;\r\n        head ++;\r\n    }\r\n}\r\n\r\nint main(){\r\n    int T; cin >> T;\r\n    while (T--){\r\n        init(); bfs();\r\n    }\r\n}\r\n<\/pre>\n<pre lang=\"cpp\" file=\"bibfs.cpp\">\r\n#include <iostream>\r\n#define label exitus\r\nusing namespace std;\r\nconst int F[9] = {1,1,2,6,24,120,720,5040,40320}, FOUND = 3;\r\nint queue[2][362880], dist[2][362880], hash[362880];\r\nint head[2], tail[2], flag;\r\nint a[9], b[2]; bool c[9];\r\n\r\nint cantor(){\r\n    int x = 0, t, i, j;\r\n    for (i=0;i<9;i++){\r\n        for (j=i+1,t=0;j<9;j++)\r\n            if (a[i]>a[j]) t++;\r\n        x = x * (9-i)  + t;\r\n    }\r\n    return x;\r\n}\r\n\r\nvoid recover(int x){\r\n    memset(c, false, sizeof(c));\r\n    memset(a, 0, sizeof(a));\r\n    int i;\r\n    for (i=0;i<9;i++){\r\n        while (c[a[i]]) a[i]++;\r\n        while (x >= F[8-i]){\r\n            x -= F[8-i]; a[i]++;\r\n            while (c[a[i]]) a[i]++;\r\n        }\r\n        c[a[i]] = true;\r\n    }\r\n}\r\n\r\nint stat(){\r\n    int  inversion_pair = 0;\r\n    for (int i=0;i<8;i++){\r\n        if (a[i]==0) continue;\r\n        for (int j=i+1;j<9;j++){\r\n            if (a[j]==0) continue;\r\n            if (a[i]>a[j]) inversion_pair++;\r\n        }\r\n    }\r\n    return inversion_pair;\r\n}\r\n\r\n\r\n\r\n\r\nvoid init(){\r\n    \r\n    int i;\r\n    \r\n    for (i=0;i<9;i++) cin >> a[i];\r\n    queue[0][0] = cantor(); b[0] = stat();\r\n    \r\n    for (i=0;i<9;i++) cin >> a[i];\r\n    queue[1][0] = cantor(); b[1] = stat();\r\n}\r\n\r\ninline void operate(int x, int y){\r\n    swap(a[x], a[y]); queue[flag][tail[flag]] = cantor(); swap(a[x], a[y]);\r\n    \r\n    if (hash[queue[flag][tail[flag]]]==flag) return ;\r\n    dist[flag][tail[flag]] = dist[flag][head[flag]] + 1;\r\n    if (hash[queue[flag][tail[flag]]]== 1 - flag){\r\n        int pos;\r\n        for (pos=head[1-flag];queue[1-flag][pos]!=queue[flag][tail[flag]];pos++);\r\n        cout << dist[flag][tail[flag]] + dist[1 - flag][pos] << endl;\r\n        flag = FOUND;\r\n        return;\r\n    }\r\n    \r\n    hash[queue[flag][tail[flag]++]] = flag;\r\n    return ;\r\n}\r\n\r\ninline void expand(){\r\n    int p; recover(queue[flag][head[flag]]);\r\n    for (p=0;a[p]!=0;p++);\r\n    if (p > 2) {operate(p, p-3); if (flag == FOUND) return;}\r\n    if (p < 6) {operate(p, p+3); if (flag == FOUND) return;}\r\n    if (p % 3) {operate(p, p-1); if (flag == FOUND) return;}\r\n    if ((p+1) % 3) {operate(p, p+1); if (flag == FOUND) return;}\r\n    head[flag]++;\r\n}\r\n\r\nvoid bibfs(){\r\n    if (queue[0][0] == queue[1][0]) {cout << 0 << endl; return;}\r\n    if (b[0]%2!=b[1]%2) {cout << -1 << endl; return;}\r\n    \r\n    dist[0][0] = dist[1][0] = 0; head[0] = head[1] = 0; tail[0] = tail[1] = 1;\r\n    memset(hash, -1, sizeof(hash)); hash[queue[0][0]] = 0; hash[queue[1][0]] = 1;\r\n    \r\n    while (true){\r\n        \r\n        \/\/if (head[0]<tail[0] &#038;&#038; head[0]<=head[1]||head[1]==tail[1]) {flag = 0; expand(); if (flag == FOUND) return;}\r\n        \/\/if (head[1]<tail[1] &#038;&#038; head[1]<=head[0]||head[0]==tail[0]) {flag = 1; expand(); if (flag == FOUND) return;}\r\n        \r\n        flag = head[0] == tail[0] || tail[1] - head[1] < tail[0] - head[0];\r\n        expand(); if (flag == FOUND) return;\r\n    }\r\n}\r\n\r\nint main(){\r\n    \r\n    ios::sync_with_stdio(false);\r\n    \r\n    int T; cin >> T;\r\n    while (T--){\r\n        init(); bibfs();\r\n    }\r\n}<\/pre>\n<pre lang=\"cpp\" file=\"Astar.cpp\">\r\n#include <iostream>\r\n#include <queue>\r\n#define REP(I, N) for (int I=0;I<int(N);++I)\r\n#define REP_1(I, N) for (int I=1;I<=int(N);++I)\r\nusing namespace std;\r\nconst int F[9] = {1,1,2,6,24,120,720,5040,40320};\r\nbool hash[362880]; int start, goal; bool _found;\r\nint st[9], ed[9], a[9], b[2], w[9][9]; bool c[9];\r\n\r\nstruct node{\r\n    int s, d, f;  \r\n    bool operator <(const node &#038;x) const{\r\n        return f > x.f;\r\n    }\r\n} u, v;\r\n\r\npriority_queue<node> Q;\r\n\r\n\r\n\r\n\r\n\/*\/\r\ninline int h(){\r\n    int s = 0; REP(i, 9) if (a[i] && a[i] != ed[i]) s++;\r\n    return s;\r\n}\r\n\r\n\/*\/\r\n \r\ninline int h(){\r\n    int s = 0; REP(i, 9) s += w[i][a[i]];\r\n    return s + s \/ 5; \/\/#\r\n}\r\n\/\/*\/\r\n\r\n\r\n\r\ninline int cantor(){\r\n    int x = 0, t, i, j;\r\n    for (i=0;i<9;i++){\r\n        for (j=i+1,t=0;j<9;j++)\r\n            if (a[i]>a[j]) t++;\r\n        x = x * (9-i) + t;\r\n    }\r\n    return x;\r\n}\r\n\r\ninline void recover(int x){\r\n    memset(c, false, sizeof(c));\r\n    memset(a, 0, sizeof(a));\r\n    int i;\r\n    for (i=0;i<9;i++){\r\n        while (c[a[i]]) a[i]++;\r\n        while (x >= F[8-i]){\r\n            x -= F[8-i]; a[i]++;\r\n            while (c[a[i]]) a[i]++;\r\n        }\r\n        c[a[i]] = true;\r\n    }\r\n}\r\n\r\ninline int stat(){\r\n    int  inversion_pair = 0;\r\n    for (int i=0;i<8;i++){\r\n        if (a[i]==0) continue;\r\n        for (int j=i+1;j<9;j++){\r\n            if (a[j]==0) continue;\r\n            if (a[i]>a[j]) inversion_pair++;\r\n        }\r\n    }\r\n    return inversion_pair;\r\n}\r\n\r\n\r\n\r\n\r\nvoid init(){\r\n    \r\n    REP(i, 9){cin >> st[i]; a[i] = st[i];}\r\n    start = cantor(); b[0] = stat();\r\n    \r\n    REP(i, 9){cin >> ed[i]; a[i] = ed[i];}\r\n    goal = cantor(); b[1] = stat();\r\n    \r\n    REP(i, 9) st[ed[i]] = i; \/\/ #\r\n    REP(i, 9) REP_1(j, 8) w[i][j] = abs(i\/3 - st[j]\/3) + abs(i%3 - st[j]%3);\r\n    _found = false;\r\n}\r\n\r\n\r\n\r\ninline void operate(int x, int y){\r\n    swap(a[x], a[y]), v.s = cantor();\r\n    if (!hash[v.s]){\r\n        v.d = u.d + 1;\r\n        if (v.s==goal){\r\n            cout << v.d << endl;\r\n            _found = true;\r\n        }\r\n        else {\r\n            v.f = v.d + h();\r\n            Q.push(v);\r\n        }\r\n    }\r\n    swap(a[x], a[y]);\r\n}\r\n\r\nvoid Astar(){\r\n    if (start == goal) {cout << 0 << endl; return;}\r\n    if (b[0]%2!=b[1]%2) {cout << -1 << endl; return;}\r\n    \r\n    while (!Q.empty()) Q.pop(); \/\/#\r\n    u.s = start, u.d = 0, Q.push(u);\r\n    memset(hash, false, sizeof(hash));\r\n    \r\n    int p;\r\n    while (true){\r\n        u = Q.top(); Q.pop(); if (hash[u.s]==true) continue;\r\n        hash[u.s] = true; recover(u.s);\r\n        \r\n        for (p=0;a[p]!=0;p++);\r\n        if (p > 2) operate(p, p-3);\r\n        if (p < 6) operate(p, p+3);\r\n        if (p % 3) operate(p, p-1);\r\n        if ((p+1) % 3) operate(p, p+1);\r\n        if (_found) return;\r\n    }\r\n}\r\n\r\nint main(){\r\n    int T; cin >> T;\r\n    while (T--){\r\n        init(); Astar();\r\n    }\r\n}\r\n<\/pre>\n<p><a href=\"http:\/\/acm.hit.edu.cn\/judge\/show.php?Proid=1868&#038;Contestid=0\"><br \/>\nhttp:\/\/acm.hit.edu.cn\/judge\/show.php?Proid=1868&#038;Contestid=0<\/a><\/p>\n<p>1. \u72b6\u6001\u7684\u5b58\u50a8<br \/>\n\u72b6\u6001\u7684\u5b58\u50a8\u91c7\u7528\u5eb7\u6258\u5c55\u5f00\u5bf9\u6392\u5217\u8fdb\u884c\u7f16\u7801\u8d77\u5230 hash \u7684\u4f5c\u7528\uff0c\u552f\u4e00\u7684\u7f3a\u70b9\u5462\u5219\u662f\u5728\u5e94\u7528\u64cd\u4f5c\u7b26\u7684\u65f6\u4faf\u9700\u8981\u89e3\u7801\u6062\u590d\u4e00\u6b21\u3002<br \/>\n\uff08\u53c2\u89c1\u4ee3\u7801\u4e2d\u7684 void cantor() \u548c void recover() \u8fc7\u7a0b\u3002\u3002\u3002\u3002\u3002\uff09<\/p>\n<p>2. \u5224\u65ad\u65e0\u89e3<br \/>\n\u53e6\u4e00\u4e2a\u91cd\u8981\u7684\u60f3\u6cd5\u662f\u5229\u7528\u9006\u5e8f\u5bf9\u7684\u5947\u5076\u6027\u5c06\u72b6\u6001\u5212\u5206\u6210\u4e24\u4e2a\u7b49\u4ef7\u7c7b\uff0c\u4e0d\u540c\u7b49\u4ef7\u7c7b\u7684\u91cc\u72b6\u6001\u4e0d\u80fd\u76f8\u4e92\u8fbe\u5230\uff0c\u8fd9\u6837\u5728\u5bbd\u641c\u4e4b\u524d\u5c31\u53ef\u4ee5\u6392\u9664\u6389\u8f93\u51fa-1\u7684\u60c5\u51b5\u3002<\/p>\n<p>3. \u5173\u4e8e Astar<br \/>\n\u76ee\u524d\u5173\u4e8e Astar \u8fd8\u5b58\u5728\u4e00\u4e9b\u7591\u95ee\u6709\u5f85\u89e3\u51b3 &#8230;<br \/>\n\u5728\u8fd9\u9898\u91cc\u800c\u8a00\uff0c\u9996\u5148\u540c\u666e\u901a BFS \u7684\u4e00\u4e2a\u663e\u8457\u4e0d\u540c\uff0c\u867d\u7136\u8fb9\u6743\u503c\u90fd\u53ea\u6709\uff0b1\u800c\u5df2\uff0c\u4f46\u662f\u53ea\u80fd\u4fdd\u8bc1\u5728\u53d6\u51fa\u961f\u5217\u7684\u65f6\u4faf\u6240\u5f97\u5230\u7684\u503c\u6700\u4f18\uff0c\uff08\u8fd9\u70b9\u53c8\u7c7b\u4f3c Dijkstra \u4e86\uff09\u56e0\u6b64\u7406\u56e0\uff0c\u5728\u6bcf\u6b21\u66f4\u65b0\u72b6\u6001\u7684\u65f6\u4faf\u5148\u8981\u5224\u65ad\u8fd9\u4e2a\u72b6\u6001\u5728\u4f18\u5148\u961f\u5217\u4e2d\u662f\u5426\u5df2\u7ecf\u5b58\u5728\uff0c\u5982\u679c\u5b58\u5728\u5219\u8fdb\u884c\u6bd4\u8f83\u5e76\u66f4\u65b0\u3002\uff08\u4f46\u662f\u8fd9\u4e00\u4efd\u4ee3\u7801\u5e76\u6ca1\u6709\u8fd9\u4e48\u505a\uff0c\u800c\u662f\u8ba9\u4e24\u4e2a\u72b6\u6001\u540c\u65f6\u52a0\u5165\u5230\u7ed3\u70b9\u4e2d\uff0c\u800c\u5728\u53d6\u51fa\u961f\u5217\u7684\u65f6\u4faf\u5bf9\u72b6\u6001\u8fdb\u884c\u6807\u8bb0\uff0c\u8fd9\u6837\u4f1a\u6709\u4e00\u4e9b\u4e0d\u597d\u7684\u5730\u65b9\uff0c\u4f46\u662f\u8fd9\u662f\u5728\u7528 STL \u5199\u7684\u65f6\u4faf\u65e0\u6cd5\u83b7\u5f97 \u5806\u4e2d\u5143\u7d20\u7684 Pos \u6570\u7ec4\u800c\u91c7\u53d6\u7684\u4e00\u79cd\u66ff\u4ee3\u65b9\u5f0f\u3002\uff09<\/p>\n<p>\u53e6\u5916\uff0c\u5173\u4e8e \u516b\u6570\u7801\u95ee\u9898 \u7684\u4e24\u79cd\u542f\u53d1\u51fd\u6570\uff0c\uff08\u6bcf\u4e2a\u5143\u7d20\u5230\u81ea\u5df1\u7406\u5e94\u6240\u5728\u70b9\u7684\u54c8\u5bc6\u987f\u8ddd\u79bb\uff0c\u4ee5\u53ca\u6240\u6709\u4e0d\u5728\u81ea\u5df1\u4f4d\u7f6e\u4e0a\u7684\u6570\u3002\uff09\uff08\u6ce8\u610f\u4e0d\u80fd\u8003\u8651\u6570\u5b57 0 \uff0c\u5177\u4f53\u539f\u56e0\u3002\u3002\u3002\uff09\u4e5f\u6709\u4e00\u4e9b\u503c\u5f97\u8ba8\u8bba\u7684\u5730\u65b9\u5462\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u5176\u5b9e&#8230;\u73b0\u5728&#8230;\u552f\u4e00\u80fd\u6ee1\u8db3\u6211\u7684&#8230; \u5c31\u53ea\u6709\u7528 Astar \u628a\u5b83\u89e3\u51fa\u6765\u4e86\u3002\u3002\u3002 #include using namespace std; const int F[9] = {1,1,2,6,24,120,720,5040,40320}; int queue[362880], dist[362880]; bool hash[362880]; int head, tail, goal; int a[9], b[2]; bool c[9]; int cantor(){ int x = 0, t, i, j; for (i=0;i a[i]; goal = cantor(); b[1] = stat(); } bool operate(int x, int y){ swap(a[x], a[y]); queue[tail] = [&hellip;]<\/p>\n","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-139","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-2f","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/139","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=139"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/139\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=139"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=139"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=139"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}