{"id":91,"date":"2024-04-26T00:57:58","date_gmt":"2024-04-25T16:57:58","guid":{"rendered":"https:\/\/seanxd.com\/?p=91"},"modified":"2024-06-18T18:10:41","modified_gmt":"2024-06-18T10:10:41","slug":"zerojudge-d365","status":"publish","type":"post","link":"https:\/\/seanxd.com\/zh\/zerojudge-d365\/","title":{"rendered":"ZeroJudge D365: Rank the Languages"},"content":{"rendered":"\n\n\n

\u540c\u984c\uff1aUVa 10336\uff0dRank the Languages<\/h4>\n\n\n\n

\u4f60\u53ef\u80fd\u6709\u6ce8\u610f\u5230\u4e16\u754c\u4e0a\u6709\u8a31\u591a\u5730\u5340\u4f7f\u7528\u82f1\u8a9e\u53ca\u897f\u73ed\u7259\u8a9e\u3002\u73fe\u5728\u6211\u5011\u5c31\u8981\u4f86\u5c0d\u4e16\u754c\u4e0a\u6240\u6709\u5730\u5340\u4f7f\u7528\u7684\u8a9e\u8a00\u4f5c\u500b\u6392\u884c\u699c\u3002<\/p>\n\n\n\n

\u4f60\u6703\u7d66\u4e00\u500b\u5730\u5716\uff0c\u5728\u4e0a\u9762\u6703\u6a19\u793a\u5404\u5730\u5340\u4ee5\u5e7e\u4ed6\u5011\u6240\u4f7f\u7528\u7684\u8a9e\u8a00\u3002\u8acb\u770b\u4ee5\u4e0b\u7684\u5730\u5716 (\u8868\u683c)\uff1a<\/p>\n\n\n\n

t<\/td>t<\/td>u<\/td>u<\/td>t<\/td>t<\/td>d<\/td>d<\/td><\/tr>
t<\/td>t<\/td>u<\/td>u<\/td>t<\/td>t<\/td>d<\/td>d<\/td><\/tr>
u<\/td>u<\/td>t<\/td>t<\/td>u<\/td>u<\/td>d<\/td>d<\/td><\/tr>
u<\/td>u<\/td>t<\/td>t<\/td>u<\/td>u<\/td>d<\/td>d<\/td><\/tr><\/tbody><\/table>
\u6211\u662f\u5730\u5716<\/figcaption><\/figure>\n\n\n\n

\u6bcf\u500b\u5b57\u5143\u4ee3\u8868\u4e00\u7a2e\u8a9e\u8a00\uff0c\u4e26\u4e14\u5340\u57df\u88ab\u5b9a\u7fa9\u70ba\u540c\u4e00\u500b\u5b57\u5143\u76f8\u9023\u7684\u5730\u5340\u30022\u500b\u5b57\u5143”\u76f8\u9023”\u6307\u7684\u662f\u8a722\u5b57\u5143\u6709\u4e0a\u3001\u4e0b\u3001\u5de6\u3001\u53f3\u56db\u500b\u65b9\u5411\u9130\u8fd1\u7684\u95dc\u4fc2\u3002\u6240\u4ee5\u5728\u4e0a\u5716\u4e2d\u67093\u500b\u5340\u57df\u8aaa t \u8a9e\u8a00\uff0c\u67093\u500b\u5340\u57df\u8aaa u \u8a9e\u8a00\uff0c\u67091\u500b\u5340\u57df\u8aaa d \u8a9e\u8a00\u3002<\/p>\n\n\n\n

\u4f60\u7684\u4efb\u52d9\u5c31\u662f\u8981\u627e\u51fa\u5730\u5716\u4e2d\u6bcf\u7a2e\u8a9e\u8a00\u88ab\u8aaa\u7684\u5340\u57df\u6578\uff0c\u4e26\u4e14\u6309\u7167\u4e00\u5b9a\u7684\u9806\u5e8f\u8f38\u51fa\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>
\u8f38\u5165\u7684\u7b2c\u4e00\u5217\u6709\u4e00\u500b\u6574\u6578 N
\u4ee3\u8868\u4ee5\u4e0b\u6709\u5e7e\u7d44\u6e2c\u8a66\u8cc7\u6599
\u6bcf\u7d44\u6e2c\u8a66\u8cc7\u6599\u7684\u7b2c\u4e00\u5217\u6709 2 \u500b\u6574\u6578 H \u53ca W<\/strong>
\u4ee3\u8868\u6b64\u5730\u5716\u7684\u9ad8\u5ea6\u53ca\u5bec\u5ea6
\u63a5\u4e0b\u4f86\u7684 H<\/strong> \u5217\u6bcf\u5217\u6709 W<\/strong> \u500b\u5b57\u5143
\u6240\u6709\u7684\u5b57\u5143\u5747\u70ba\u5c0f\u5beb\u7684\u82f1\u6587\u5b57\uff08a~z\uff09<\/td>		\u5c0d\u6bcf\u7d44\u6e2c\u8a66\u8cc7\u6599
\u5148\u8f38\u51fa “World #N”
N \u662f\u7b2c\u5e7e\u7d44\u6e2c\u8a66\u8cc7\u6599
\u63a5\u4e0b\u4f86\u8f38\u51fa\u5728\u6b64\u5730\u5716\u4e2d\u6bcf\u7a2e\u8a9e\u8a00\u88ab\u8aaa\u7684\u5340\u57df\u6578 (\u8acb\u7531\u5927\u5230\u5c0f\u6392\u5217)
\u5982\u679c\u67092\u7a2e\u8a9e\u8a00\u5340\u57df\u6578\u76f8\u540c
\u8acb\u4f9d\u82f1\u6587\u5b57\u7684\u9806\u5e8f\u8f38\u51fa (\u4f8b\u5982i\u8a9e\u8a00\u8981\u5728q\u8a9e\u8a00\u4e4b\u524d)<\/td><\/tr>
2
4 8<\/strong>
ttuuttdd
ttuuttdd
uuttuudd
uuttuudd
9 9<\/strong>
bbbbbbbbb
aaaaaaaab
bbbbbbbab
baaaaacab
bacccccab
bacbbbcab
bacccccab
baaaaaaab
bbbbbbbbb<\/td>		World #1
t: 3
u: 3
d: 1
World #2
b: 2
a: 1
c: 1<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

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

\u4f7f\u7528DFS<\/strong>\u4f86\u5c07\u6bcf\u4e00\u500b\u9ede\u8d70\u904e\u4e00\u904d\u4f86\u78ba\u8a8d\u5730\u5716\u4e0a\u6709\u5e7e\u500b\u4e0d\u540c\u5b57\u5143\u7684\u5730\u5340<\/strong>\uff0c\u53ef\u4ee5\u7528Map<\/strong>\u7684\u65b9\u5f0f\u628a\u5b57\u5143\u7684\u5730\u5340\u6578\u91cf\u5b58\u8d77\u4f86\u3002\u9700\u8981\u6ce8\u610f\u7684\u662f\uff0c\u9700\u8981\u6709\u4e00\u500b\u9663\u5217\u4f86\u7d00\u9304\u8d70\u904e\u7684\u6bcf\u4e00\u500b\u9ede\u4f86\u907f\u514dDFS\u91cd\u8907\u8a08\u7b97<\/strong>\u7684\u60c5\u6cc1\u3002\u8f38\u51fa\u7684\u6642\u5019\u8981\u6309\u7167\u5730\u5340\u7684\u6578\u91cf\u7531\u5927\u5230\u5c0f\u8f38\u51fa\uff0c\u9019\u6642\u53ef\u4ee5\u5c07\u6bcf\u4e00\u500b\u5b57\u5143\u548c\u5730\u5340\u6578\u91cf\u5b58\u5728\u4e00\u500bPair<\/strong>\u88e1\u9762\uff0c\u7b2c\u4e00\u500b\u6b04\u4f4d\u5b58int\uff0c\u7b2c\u4e8c\u500b\u6b04\u4f4d\u5b58\u5b57\u5143\uff0c\u4e26\u628a\u9019\u4e9bPair\u5b58\u5728\u9663\u5217\u88e1\uff0c\u9019\u6a23\u5c31\u53ef\u4ee5\u7528Sort<\/strong>\u4f86\u6392\u5e8f\u8981\u8f38\u51fa\u7684\u8cc7\u6599\uff0c\u6700\u5f8c\u7528For<\/strong>\u8ff4\u5708\u4f9d\u5e8f\u8f38\u51fa\u3002<\/p>\n\n\n\n

\u7bc4\u4f8b\u7a0b\u5f0f\u78bc\uff0dZeroJudge D365: Rank the Languages<\/a><\/h3>\n\n\n\n
#include <iostream>\n#include <vector>\n#include <map>\n#include <algorithm>\nusing namespace std;\n\nvector<string>str;\nvector<vector<int>>walk;\nint H, W;\n\nvoid DFS(int y, int x)\n{\n    if (walk[y][x] == 1) return;\n    else\n    {\n        walk[y][x] = 1;\n        if (y-1 >= 0 && walk[y-1][x] == 0 && str[y-1][x] == str[y][x])\n        {\n            DFS(y-1, x);\n        }\n        if (y+1 < H && walk[y+1][x] == 0 && str[y+1][x] == str[y][x])\n        {\n            DFS(y+1, x);\n        }\n        if (x-1 >= 0 && walk[y][x-1] == 0 && str[y][x-1] == str[y][x])\n        {\n            DFS(y, x-1);\n        }\n        if (x+1 < W && walk[y][x+1] == 0 && str[y][x+1] == str[y][x])\n        {\n            DFS(y, x+1);\n        }\n    }\n}\n\nint main() {\n    int N;\n    cin >> N;\n    for (int i = 0; i<N; i++)\n    {\n        cin >> H >> W;\n        str.clear();\n        walk.clear();\n        map<char, int>MAP;\n        for (int j = 0; j<H; j++)\n        {\n            string tmp;\n            cin >> tmp;\n            str.push_back(tmp);\n            vector<int>it;\n            for (int k = 0; k<W; k++)\n            {\n                it.push_back(0);\n            }\n            walk.push_back(it);\n        }\n        vector<char>ch;\n        for (int j = 0; j<H; j++)\n        {\n            for (int k = 0; k<W; k++)\n            {\n                if (walk[j][k] == 0)\n                {\n                    char tmp = str[j][k];\n                    DFS(j, k);\n                    if (MAP[tmp] == 0) ch.push_back(tmp);\n                    MAP[tmp]++;\n                }\n            }\n        }\n        cout << "World #" << i+1 << endl;\n        vector<pair<int, char>>ans;\n        for (int j = 0; j<ch.size(); j++)\n        {\n            pair<int, char>tmp;\n            tmp.second = ch[j];\n            tmp.first = MAP[ch[j]] * -1;\n            ans.push_back(tmp);\n        }\n        sort(ans.begin(), ans.end());\n        for (int j = 0; j<ans.size(); j++)\n        {\n            cout << ans[j].second << ": " << ans[j].first*-1 << endl;\n        }\n    }\n}\n\n\/\/ZeroJudge D365\n\/\/Dr. SeanXD<\/code><\/pre><\/div>\n","protected":false},"excerpt":{"rendered":"
\u540c\u984c\uff1aUVa 10336\uff0dRank the Languages \u4f60\u53ef\u80fd\u6709\u6ce8\u610f\u5230\u4e16\u754c\u4e0a\u6709\u8a31\u591a\u5730\u5340\u4f7f\u7528\u82f1\u8a9e\u53ca\u897f\u73ed\u7259 […]<\/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":[21,14,23,22,8,11,19,9],"class_list":["post-91","post","type-post","status-publish","format-standard","hentry","category-uva","tag-dfs","tag-map","tag-pair","tag-22","tag-8","tag-11","tag-19","tag-9"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts\/91","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=91"}],"version-history":[{"count":4,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts\/91\/revisions"}],"predecessor-version":[{"id":958,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts\/91\/revisions\/958"}],"wp:attachment":[{"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/media?parent=91"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/categories?post=91"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/tags?post=91"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}