{"id":731,"date":"2024-07-13T09:00:00","date_gmt":"2024-07-13T01:00:00","guid":{"rendered":"https:\/\/seanxd.com\/?p=731"},"modified":"2024-06-05T17:55:20","modified_gmt":"2024-06-05T09:55:20","slug":"zerojudge-c117","status":"publish","type":"post","link":"https:\/\/seanxd.com\/zh\/zerojudge-c117\/","title":{"rendered":"ZeroJudge C117: Knight Moves"},"content":{"rendered":"\n\n\n

\u540c\u984c\uff1aUVa 00439 – Knight Moves<\/h4>\n\n\n\n

\u4f60\u7684\u4e00\u500b\u670b\u53cb\u6b63\u5728\u505a\u4e00\u500b\u95dc\u65bc\u897f\u6d0b\u68cb\u4e2d\u9a0e\u58eb\u65c5\u884c\u554f\u984c (Traveling Knight Problem) \u7684\u7814\u7a76\uff0c\u4ed6\u5e0c\u671b\u4f60\u5e6b\u4ed6\u89e3\u6c7a\u4e00\u500b\u554f\u984c\uff1a\u5c31\u662f\u7d66\u4f60 2 \u500b\u683c\u5b50\u7684\u4f4d\u7f6e X \u53ca Y\uff0c\u8acb\u4f60\u627e\u51fa\u9a0e\u58eb\u5f9e X \u8d70\u5230 Y \u6700\u5c11\u9700\u8981\u8d70\u5e7e\u6b65<\/strong>\u3002<\/p>\n\n\n\n

\u7bc4\u4f8b\u6e2c\u8cc7<\/h2>\n\n\n\n
\u7bc4\u4f8b\u8f38\u5165<\/th>\u7bc4\u4f8b\u8f38\u51fa<\/th><\/tr><\/thead>
EOF \u8f38\u5165<\/strong>\uff0c\u6bcf\u7b46\u6e2c\u8a66\u8cc7\u6599\u4e00\u5217\u3002\u6bcf\u5217\u6709 2 \u500b\u897f\u6d0b\u68cb\u7684\u5ea7\u6a19\u4f4d\u7f6e\u3002\u6bcf\u500b\u4f4d\u7f6e\u5ea7\u6a19\u662f\u7531\u4e00\u500b\u82f1\u6587\u5b57\u6bcd (a\uff5eh\uff0c\u4ee3\u8868\u68cb\u76e4\u7684\u7b2c\u5e7e\u6b04) \u53ca\u4e00\u500b\u6578\u5b57 (1\uff5e8\uff0c\u4ee3\u8868\u68cb\u76e4\u7684\u7b2c\u5e7e\u5217) \u7d44\u6210\u3002<\/td>\u5c0d\u6bcf\u4e00\u5217\u8f38\u5165\uff0c\u8acb\u8f38\u51fa\u300cTo get from xx to yy takes N knight moves.\u300d\u3002<\/td><\/tr>
e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6<\/td>		To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.<\/td><\/tr><\/tbody><\/table>
ZeroJudge C117 \u7bc4\u4f8b\u6e2c\u8cc7<\/figcaption><\/figure>\n\n\n\n

\u89e3\u984c\u601d\u8def<\/h2>\n\n\n\n

\u6536\u8cc7\u6599\u7684\u6642\u5019\u4f7f\u7528\u5169\u500b\u5b57\u4e32\u5c07\u8d77\u9ede\u8ddf\u7d42\u9ede\u6536\u8d77\u4f86\uff0c\u53ef\u4ee5\u4f7f\u7528 Pair<int, int> \u4f86\u5b58\uff0cPair.first \u5c31\u6703\u662f\u6578\u5b57\u7684\u90e8\u5206\uff0cPair.second \u6703\u662f \u5b57\u6bcd\u7684\u90e8\u5206\uff0c\u53ef\u4ee5\u7528\u300c\u5b57\u6bcd – ‘a’ + 1\u300d\u5c07\u5b57\u6bcd\u63db\u6210\u6578\u5b57\uff0c\u8a18\u5f97\u8981+1\u56e0\u70baBFS\u8dd1\u7684\u662f 1-Base\u3002<\/p>\n\n\n\n

\u8ddf\u666e\u901a\u7684 BFS \u6982\u5ff5\u76f8\u540c\uff0c\u53ea\u662f\u4e0d\u662f\u4e0a\u4e0b\u5de6\u53f3\u8d70\uff0c\u8981\u7528\u897f\u6d0b\u68cb\u7684\u9a0e\u58eb\u7684\u8d70\u6cd5\u8d70 BFS\uff0c\u53ef\u4ee5\u5ba3\u544a\u4e00\u500b\u9663\u5217 int loc[8][2] = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}}\uff0c\u9019\u4e9b\u5c31\u662f\u9a0e\u58eb\u7684\u8d70\u6cd5\uff0c\u8a18\u5f97\u4e0d\u80fd\u91cd\u8907\u8d70\u5230\u76f8\u540c\u7684\u9ede\u4e0a\uff0c\u53ef\u4ee5\u4f7f\u7528 Map \u4f86\u7d00\u9304\u3002<\/p>\n\n\n\n

\u53ef\u4ee5\u9810\u8a2d\u4e00\u500b count \u8b8a\u6578\u70ba 0\uff0c\u6bcf\u4e00\u6b21\u91cd\u65b0\u547c\u53eb BFS \u6642\u5c31\u5c07 count++\u3002\u7576\u627e\u5230\u7d42\u9ede\u4e86\u5c31 return count\u3002<\/p>\n\n\n\n

\u7bc4\u4f8b\u7a0b\u5f0f\u78bc\uff0dZeroJudge C117: Knight Moves<\/a><\/h3>\n\n\n\n
#include <iostream>\n#include <map>\n#include <vector>\nusing namespace std;\n\npair<int, int> start, finish;\nint loc[8][2] = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};\n\npair<int, int> axis (const int a, const int b) {\n    pair<int, int>tmp;\n    tmp.first = a;\n    tmp.second = b;\n    return tmp;\n}\n\nint BFS(const vector<pair<int, int>>&start, map<pair<int, int>, int>MAP, int count) {\n    if (start.size() == 0) return count;\n    vector<pair<int, int>>newStart;\n    for (auto & i : start) {\n        MAP[i]++;\n        if (i == finish) return count;\n        const int y = i.first, x = i.second;\n        for (int j = 0; j<8; j++) {\n            const int yy = y+loc[j][0], xx = x+loc[j][1];\n            if (yy > 0 && yy <= 8 && xx > 0 && xx <= 8 && MAP[axis(yy, xx)] == 0) {\n                newStart.push_back(axis(yy, xx));\n            }\n        }\n    }\n    return BFS(newStart, MAP, count+1);\n}\n\nint main() {\n    cin.sync_with_stdio(0);\n    cin.tie(0);\n    string a, b;\n    while (cin >> a >> b) {\n        start = axis(a[1] - '0', a[0] - 'a' + 1);\n        finish = axis(b[1] - '0', b[0] - 'a' + 1);\n        vector<pair<int, int>>begin;\n        begin.push_back(start);\n        map<pair<int, int>, int>MAP;\n        cout << "To get from " << a << " to " << b << " takes " << BFS(begin, MAP, 0) << " knight moves.\\n";\n    }\n}\n\n\/\/ZeroJudge C117\n\/\/Dr. SeanXD<\/code><\/pre><\/div>\n","protected":false},"excerpt":{"rendered":"
\u540c\u984c\uff1aUVa 00439 – Knight Moves \u4f60\u7684\u4e00\u500b\u670b\u53cb\u6b63\u5728\u505a\u4e00\u500b\u95dc\u65bc\u897f\u6d0b\u68cb\u4e2d\u9a0e\u58eb\u65c5\u884c […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","footnotes":""},"categories":[18],"tags":[30,14,23,20,8,11,12,9],"class_list":["post-731","post","type-post","status-publish","format-standard","hentry","category-uva","tag-bfs","tag-map","tag-pair","tag-20","tag-8","tag-11","tag-12","tag-9"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts\/731","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/comments?post=731"}],"version-history":[{"count":2,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts\/731\/revisions"}],"predecessor-version":[{"id":733,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts\/731\/revisions\/733"}],"wp:attachment":[{"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/media?parent=731"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/categories?post=731"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/tags?post=731"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}