{"id":366,"date":"2024-04-28T21:25:09","date_gmt":"2024-04-28T13:25:09","guid":{"rendered":"https:\/\/seanxd.com\/?p=366"},"modified":"2024-04-28T21:25:12","modified_gmt":"2024-04-28T13:25:12","slug":"zerojudge-f671","status":"publish","type":"post","link":"https:\/\/seanxd.com\/zh\/zerojudge-f671\/","title":{"rendered":"ZeroJudge F671: \u6700\u77ed\u8def\u5f91"},"content":{"rendered":"\n\n\n

\u300c\u7121\u984c\u76ee\u5167\u5bb9\u300d<\/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 1 \u884c\u7d66\u5b9a\u5169\u500b\u6574\u6578 N \u548c M (1 <= N, M <= 10) \u8868\u793a\u70ba\u4e00\u500b\u8868\u793a\u70ba\u4e00\u500b N\uff0aM \u7684\u7db2\u683c\uff0c\u7b2c 2 \u5230 N+1 \u884c\u6bcf\u884c\u6709 M \u500b\u5b57\u5143\uff0c\u5b57\u5143\u53ef\u70ba\u300c.\u300d(\u4ee3\u8868\u8def) \u6216\u300c#\u300d(\u4ee3\u8868\u969c\u7919)\uff0c\u5728\u8def\u4e0a\u53ef\u4ee5\u4e0a\u4e0b\u5de6\u53f3\u7684\u8d70\uff0c\u4f46\u4e0d\u80fd\u8d85\u51fa\u908a\u754c\u3002<\/td>\u8f38\u51fa\u5f9e\u5de6\u4e0a\u89d2 (1, 1) \u8d70\u5230\u53f3\u4e0b\u89d2 (N, M) \u6700\u5c11\u9700\u8981\u82b1\u591a\u5c11\u6b65\uff0c\u5982\u679c\u8d70\u4e0d\u5230\uff0c\u8acb\u8f38\u51fa -1\u3002<\/td><\/tr>
3 5
(\u8acb\u898b\u4e0b\u65b9\u8868\u683c)<\/td>		10<\/td><\/tr><\/tbody><\/table>
ZeroJudge F671 \u7bc4\u4f8b\u6e2c\u8cc7<\/figcaption><\/figure>\n\n\n\n

\u7bc4\u4f8b\u8f38\u5165<\/h3>\n\n\n\n
.<\/td>#<\/td>.<\/td>.<\/td>.<\/td><\/tr>
.<\/td>#<\/td>.<\/td>#<\/td>.<\/td><\/tr>
.<\/td>.<\/td>.<\/td>#<\/td>.<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

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

\u53ef\u4ee5\u8a2d\u5b9a\u4e00\u500b\u70ba 99999 \u7684\u8b8a\u6578\u7528\u4f86\u6bd4\u8f03\u6700\u77ed\u8ddd\u96e2<\/strong>\uff0c\u4e26\u4e14\u4f7f\u7528 BFS \u7684\u65b9\u5f0f\u9032\u884c\u6700\u77ed\u8ddd\u96e2\u7684\u5224\u65b7<\/strong>\uff0c\u5982\u679c\u8dd1\u5b8c BFS \u4e4b\u5f8c\u8b8a\u6578\u9084\u662f 99999 \u4ee3\u8868\u7121\u6cd5\u8d70\u5230\u9019\u500b\u9ede\u5247\u8f38\u51fa -1<\/strong>\u3002<\/p>\n\n\n\n

\u7bc4\u4f8b\u7a0b\u5f0f\u78bc\uff0dZeroJudge F671: \u6700\u77ed\u8def\u5f91<\/a><\/h3>\n\n\n\n
#include <iostream>\n#include <vector>\n#include <map>\nusing namespace std;\n\nint N, M, ans = 99999;\nvector<string>v;\nmap<pair<int, int>, int>MAP;\n\npair<int, int> axis (int a, int b)\n{\n    pair<int, int>tmp;\n    tmp.first = a;\n    tmp.second = b;\n    return tmp;\n}\n\nvoid BFS(vector<pair<int, int>>start, int count)\n{\n    if (start.size() == 0) return;\n    vector<pair<int, int>>newStart;\n    count++;\n    for (int i = 0; i<start.size(); i++)\n    {\n        int x = start[i].second, y = start[i].first;\n        MAP[axis(y, x)]++;\n        if (y == N-1 && x == M-1)\n        {\n            if (count < ans) ans = count;\n            return;\n        }\n        if (y + 1 < N && MAP[axis(y+1, x)] == 0 && v[y+1][x] != '#') newStart.push_back(axis(y+1, x));\n        if (y - 1 >= 0 && MAP[axis(y-1, x)] == 0 && v[y-1][x] != '#') newStart.push_back(axis(y-1, x));\n        if (x + 1 < M && MAP[axis(y, x+1)] == 0 && v[y][x+1] != '#') newStart.push_back(axis(y, x+1));\n        if (x - 1 >= 0 && MAP[axis(y, x-1)] == 0 && v[y][x-1] != '#') newStart.push_back(axis(y, x-1));\n    }\n    BFS(newStart, count);\n}\n\nint main() {\n    cin.sync_with_stdio(0);\n    cin.tie(0);\n    cin >> N >> M;\n    for (int i = 0; i<N; i++)\n    {\n        string str;\n        cin >> str;\n        v.push_back(str);\n    }\n    vector<pair<int, int>>tmp;\n    tmp.push_back(axis(0, 0));\n    BFS(tmp, 0);\n    if (ans == 99999) cout << -1 << "\\n";\n    else cout << ans-1 << "\\n";\n}\n\n\/\/ZeroJudge F671\n\/\/Dr. SeanXD<\/code><\/pre><\/div>\n","protected":false},"excerpt":{"rendered":"
\u300c\u7121\u984c\u76ee\u5167\u5bb9\u300d \u7bc4\u4f8b\u6e2c\u8cc7 \u7bc4\u4f8b\u8f38\u5165 \u7bc4\u4f8b\u8f38\u51fa \u7b2c 1 \u884c\u7d66\u5b9a\u5169\u500b\u6574\u6578 N \u548c M (1 <= N, M  […]<\/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":[29],"tags":[30,14,23,20,8,11,9],"class_list":["post-366","post","type-post","status-publish","format-standard","hentry","category-zerojudge-","tag-bfs","tag-map","tag-pair","tag-20","tag-8","tag-11","tag-9"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts\/366","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=366"}],"version-history":[{"count":2,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts\/366\/revisions"}],"predecessor-version":[{"id":368,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts\/366\/revisions\/368"}],"wp:attachment":[{"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/media?parent=366"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/categories?post=366"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/tags?post=366"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}