{"id":1277,"date":"2024-11-23T09:00:00","date_gmt":"2024-11-23T01:00:00","guid":{"rendered":"https:\/\/seanxd.com\/?p=1277"},"modified":"2024-11-02T09:45:22","modified_gmt":"2024-11-02T01:45:22","slug":"zerojudge-o712","status":"publish","type":"post","link":"https:\/\/seanxd.com\/en\/zerojudge-o712\/","title":{"rendered":"ZeroJudge O712: Searching Gems"},"content":{"rendered":"\n\n\n

\u6709\u4e00\u500b M \u00d7 N \u7684\u5730\u5716\uff0c\u6bcf\u4e00\u683c\u7684\u6578\u5b57\u7d00\u9304\u8457\u5bf6\u77f3\u7684\u6578\u91cf\uff0c\u5982\u679c\u6578\u5b57\u662f -1 \u4ee3\u8868\u7246\u58c1\u3002<\/p>\n\n\n\n

\u6709\u4e00\u4f4d\u6a5f\u5668\u4eba\u4e00\u958b\u59cb\u4f4d\u65bc (r, c) \u7684\u4f4d\u7f6e\u4e0a\u4e14\u65b9\u5411\u671d\u53f3\u908a\uff0c\u4ed6\u9075\u5faa\u8457\u4ee5\u4e0b\u898f\u5247\u884c\u8d70\u3002<\/p>\n\n\n\n

    \n
  1. \u82e5\u6a5f\u5668\u4eba\u4f4d\u65bc\u7684\u683c\u5b57\u5167\u5bf6\u77f3\u6578\u91cf\u70ba 0\uff0c\u5247\u6a5f\u5668\u4eba\u7a0b\u5f0f\u7d42\u6b62\u3002<\/li>\n\n\n\n
  2. \u6a5f\u5668\u4eba\u7dad\u8b77\u8457\u4e00\u500b\u5206\u6578 score\uff0c\u5c07 score \u52a0\u4e0a\u7576\u524d\u683c\u7684\u5bf6\u77f3\u6578\u91cf\uff0c\u4e26\u4e14\u64bf\u8d77 1 \u9846\u5bf6\u77f3\u3002<\/li>\n\n\n\n
  3. \u82e5 score \u662f k \u7684\u500d\u6578\uff0c\u5247\u5411\u53f3\u8f49 90 \u5ea6\u3002<\/li>\n\n\n\n
  4. \u82e5\u6a5f\u5668\u4eba\u9762\u5411\u7684\u683c\u5b50\u662f\u7246\u58c1\u6216\u662f\u8d85\u51fa\u908a\u754c\uff0c\u5247\u7e7c\u7e8c\u5411\u53f3\u8f49 90 \u5ea6\u76f4\u5230\u9762\u5411\u7684\u683c\u5b50\u975e\u7246\u58c1\u6216\u975e\u8d85\u51fa\u908a\u754c\uff0c\u4e26\u56de\u5230\u7b2c 1 \u6b65\u3002<\/li>\n<\/ol>\n\n\n\n
    \"ZeroJudge<\/figure>\n\n\n\n

    \u4f8b\u5982\u6a5f\u5668\u4eba\u4e00\u958b\u59cb\u5728\u5ea7\u6a19 (2, 1) \u4e14 k = 2\uff0c\u5411\u53f3\u8d70\u5169\u6b65\u4e4b\u5f8c\u5206\u6578\u70ba 3 + 2 + 3 = 8\uff0c\u7531\u65bc 8 \u662f 2 (k = 2) \u7684\u500d\u6578\u6240\u4ee5\u5411\u53f3\u8f49 90 \u5ea6\u3002\u63a5\u4e0b\u4f86\u5f80\u4e0b\u8d70\u4e00\u6b65\u5206\u6578\u8b8a\u70ba 11\uff0c\u9700\u8981\u5411\u53f3\u8f49 2 \u6b21 90 \u5ea6\u624d\u4e0d\u6703\u9762\u5411\u7246\u58c1\u6216\u662f\u908a\u754c\u5916\u7684\u683c\u5b50\u3002<\/p>\n\n\n\n

    \u63a5\u4e0b\u4f86\u5411\u524d\u8d70\u4e00\u6b65\u8d70\u5230\u5ea7\u6a19 (2, 3)\uff0c\u7531\u65bc\u5148\u524d\u5df2\u7d93\u62ff\u8d70\u4e00\u9846\u5bf6\u77f3\uff0c\u8a72\u4f4d\u7f6e\u7684\u5bf6\u77f3\u6578\u91cf\u8b8a\u70ba 2\uff0c\u56e0\u6b64\u5206\u6578\u8b8a\u70ba 13\uff0c\u518d\u7e7c\u7e8c\u5f80\u4e0a\u8d70\u5169\u6b65\u5230 (0, 3) \u8655\u5206\u6578\u70ba 16\uff0c\u7531\u65bc 16 \u70ba 2 (k = 2) \u7684\u500d\u6578\u6240\u4ee5\u5411\u53f3\u8f49 90 \u5ea6\u3002<\/p>\n\n\n\n

    \u5411\u524d\u8d70\u4e00\u683c\u5230 (0, 4) \u5f8c\u9700\u8981\u5411\u53f3\u8f49\u5169\u6b21 90 \u5ea6\uff0c\u56de\u5230 (0, 3) \u5f8c\u7531\u65bc\u5bf6\u77f3\u6578\u91cf\u70ba 0\uff0c\u6a5f\u5668\u4eba\u505c\u6b62\u3002\u904e\u7a0b\u4e2d\u6a5f\u5668\u4eba\u7e3d\u5171\u64bf\u4e86 8 \u9846\u5bf6\u77f3\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>
    \u7b2c\u4e00\u884c\u6709\u00a05 \u500b\u6b63\u6574\u6578\u00a0M\u3001N\u3001k\u3001r\u3001c\u3002
    1 <= M <= 100
    2 <= N <= 100
    1 <= k <= 20
    0 <= r < M
    0 <= c < N
    \u4fdd\u8b49\u6a5f\u5668\u4eba\u521d\u59cb\u4f4d\u7f6e\u4e0d\u662f\u7246\u58c1\u3002\u63a5\u4e0b\u4f86\u6709 M \u884c\uff0c\u6bcf\u4e00\u884c\u6709 N \u500b\u6578\u5b57\uff0c\u4ee3\u8868\u5730\u5716\u7684\u8cc7\u8a0a\u3002<\/td>    		\u8f38\u51fa\u6a5f\u5668\u4eba\u6703\u8490\u96c6\u5e7e\u500b\u5bf6\u77f3\u3002<\/td><\/tr>
    1 7 3 0 4
    1 -1 2 1 2 1 0<\/td>    		5<\/td><\/tr>
    4 5 4 2 1
    2 0 1 1 1
    2 -1 0 2 -1
    0 3 2 3 0
    1 1 -1 3 1<\/td>    		8<\/td><\/tr><\/tbody><\/table>
    ZeroJudge O712 \u7bc4\u4f8b\u6e2c\u8cc7<\/figcaption><\/figure>\n\n\n\n

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

    \u4f7f\u7528\u905e\u8ff4\u7684\u65b9\u5f0f\u4f9d\u7167\u984c\u76ee\u7684\u8981\u6c42\u8d70\uff0c\u905e\u8ff4\u7684\u7d42\u6b62\u689d\u4ef6\u5c31\u662f\u76ee\u524d\u8e29\u5230\u7684\u9ede\u6c92\u6709\u5bf6\u77f3\u3002<\/p>\n\n\n\n

    \u7bc4\u4f8b\u7a0b\u5f0f\u78bc\uff0dZeroJudge O712: \u8490\u96c6\u5bf6\u77f3<\/a><\/h3>\n\n\n\n
    #include <iostream>\n#include <map>\nusing namespace std;\n\nint M, N, K, R, C, maze[100][100] = {}, score = 0, gem = 0;\n\nmap<char, pair<int, int>>loc;\n\nchar turnRight(const char dir) {\n    if (dir == 'R') return 'D';\n    if (dir == 'D') return 'L';\n    if (dir == 'L') return 'U';\n    return 'R';\n}\n\nvoid walk(const int y, const int x, char dir) {\n    if (maze[y][x] == 0) return;\n    score += maze[y][x];\n    gem++;\n    maze[y][x]--;\n    if (score % K == 0) {\n        dir = turnRight(dir);\n    }\n    int yy = y + loc[dir].first, xx = x + loc[dir].second;\n    while (yy < 0 || yy >= M || xx < 0 || xx >= N || maze[yy][xx] == -1) {\n        dir = turnRight(dir);\n        yy = y + loc[dir].first, xx = x + loc[dir].second;\n    }\n    walk(yy, xx, dir);\n}\n\nint main() {\n    cin.sync_with_stdio(0);\n    cin.tie(0);\n    loc['R'] = make_pair(0, 1);\n    loc['D'] = make_pair(1, 0);\n    loc['L'] = make_pair(0, -1);\n    loc['U'] = make_pair(-1, 0);\n    cin >> M >> N >> K >> R >> C;\n    for (int i = 0; i<M; i++) {\n        for (int j = 0; j<N; j++) cin >> maze[i][j];\n    }\n    walk(R, C, 'R');\n    cout << gem << "\\n";\n}\n\n\/\/ZeroJudge O712\n\/\/Dr. SeanXD<\/code><\/pre><\/div>\n","protected":false},"excerpt":{"rendered":"
    \u6709\u4e00\u500b M \u00d7 N \u7684\u5730\u5716\uff0c\u6bcf\u4e00\u683c\u7684\u6578\u5b57\u7d00\u9304\u8457\u5bf6\u77f3\u7684\u6578\u91cf\uff0c\u5982\u679c\u6578\u5b57\u662f -1 \u4ee3\u8868\u7246\u58c1\u3002 \u6709\u4e00\u4f4d\u6a5f\u5668\u4eba\u4e00\u958b\u59cb\u4f4d\u65bc […]<\/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":[25],"tags":[14,8,11,9,28],"class_list":["post-1277","post","type-post","status-publish","format-standard","hentry","category-ioi-apcs","tag-map","tag-8","tag-11","tag-9","tag-28"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/1277","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/comments?post=1277"}],"version-history":[{"count":3,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/1277\/revisions"}],"predecessor-version":[{"id":1281,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/1277\/revisions\/1281"}],"wp:attachment":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/media?parent=1277"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/categories?post=1277"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/tags?post=1277"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}