\u4ee5\u4e0b\u7684\u5716\u986f\u793a\u51fa\u6709 4 \u689d\u6771\u897f\u5411\u7684\u9053\u8def\uff0c\u6709 5 \u689d\u5357\u5317\u5411\u7684\u9053\u8def\uff0c\u6709 3 \u500b\u5341\u5b57\u8def\u53e3\u662f\u5371\u96aa\u7684\u3002\u6240\u4ee5\u5f9e\u5de6\u4e0a\u89d2\u8d70\u5230\u53f3\u4e0b\u89d2\u8981\u8d70 (N-1)+(W-1) = 3 + 4 = 7 \u683c\u7684\u8ddd\u96e2\uff0c\u4e26\u4e14\u7e3d\u5171\u6709 4 \u7a2e\u4e0d\u540c\u7684\u8d70\u6cd5\u3002<\/p>\n\n\n\n \u6703\u6709\u300c\u8d77\u9ede\u6216\u7d42\u9ede\u662f\u5371\u96aa\u5341\u5b57\u8def\u53e3\u300d<\/strong>\u7684\u60c5\u6cc1\uff0c\u9019\u7a2e\u6642\u5019\u7b54\u6848\u5c31\u662f 0\u3002<\/p>\n\n\n\n \u5b58\u53d6\u5371\u96aa\u5341\u5b57\u8def\u53e3\u5ea7\u6a19\u6642\u53ef\u4ee5\u628a\u5ea7\u6a19\u9ede\u8f49\u63db\u6210 0-Base \u7684\u5ea7\u6a19\uff0c\u9019\u6a23\u5b50\u65b9\u4fbf\u8d70 BFS \u7684\u6642\u5f8c\u6bd4\u8f03\u597d\u5224\u65b7\u3002\u53ef\u4ee5\u4f7f\u7528\u5b57\u4e32\u7684\u65b9\u5f0f getline \u5371\u96aa\u5341\u5b57\u8def\u53e3\uff0c\u4e26\u7528 For\u8ff4\u5708 \u5c07\u88e1\u9762\u7684\u6578\u5b57\u7368\u7acb\u51fa\u4f86\u5b58\u5230\u4e00\u500b\u9663\u5217\u4e2d\u3002\u9700\u8981\u6ce8\u610f\u6e2c\u8cc7\u4e2d\u4e0d\u6703\u6309\u7167\u9806\u5e8f\u7d66\u9019\u4e9b\u5ea7\u6a19\uff0c\u6709\u53ef\u80fd\u6703\u5148\u7d66\u7b2c\u4e8c\u884c\u518d\u4f86\u662f\u7b2c\u4e00\u884c\uff0c\u6240\u4ee5\u5b58\u5ea7\u6a19\u7684\u6642\u5019\u9700\u8981\u4f7f\u7528\u90a3\u4e00\u884c\u7684\u7b2c\u4e00\u500b\u6578\u5b57\u3002<\/p>\n\n\n\n \u4f7f\u7528 BFS\uff0c\u6bcf\u6b21\u5f80\u4e0b\u6216\u662f\u5f80\u53f3\u8d70\uff0c\u4e26\u5ba3\u544a\u4e00\u500b\u4e8c\u7dad\u9663\u5217\uff0c\u88e1\u9762\u7684\u8cc7\u6599\u9810\u8a2d\u70ba 0\u3002\u8dd1 BFS \u6642\u5982\u679c\u53ef\u4ee5\u5f80\u4e0b\u6216\u5f80\u53f3\u8d70\uff0c\u5247\u5c07\u4e0b\u4e00\u500b\u9ede\u4f4d\u7f6e\u7684\u4e8c\u7dad\u9663\u5217\u503c += \u76ee\u524d\u4f4d\u7f6e\u7684\u4e8c\u7dad\u9663\u5217\u503c\u3002\u9700\u8981\u6ce8\u610f\u7684\u662f\uff0c\u5728\u5b58\u53d6\u4e0b\u4e00\u6b21 BFS \u8d77\u9ede\u7684\u6642\u5019\u4e0d\u80fd\u91cd\u8907\u5c07\u540c\u4e00\u500b\u8d77\u9ede\u5b58\u653e\u5230\u9663\u5217\u4e2d\uff0c\u6240\u4ee5\u53ef\u4ee5\u5ba3\u544a\u4e00\u500b Map \u4f86\u78ba\u8a8d\u76ee\u524d\u8981\u5b58\u7684\u8d77\u9ede\u662f\u5426\u5df2\u7d93\u88ab\u5b58\u904e\u4e86\u3002<\/p>\n\n\n\n \u7b54\u6848\u5c31\u662f\u4e8c\u7dad\u9663\u5217\u4e2d\u6700\u5de6\u4e0b\u89d2\u7684\u90a3\u500b\u8cc7\u6599\u3002<\/p>\n\n\n\n \u540c\u984c\uff1aUVa 00825 – Walking on the Safe Side \u5728\u6b63\u65b9\u57ce\u9019\u500b\u57ce\u5e02\u8d70 […]<\/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,15,14,23,20,22,8,11,9],"class_list":["post-607","post","type-post","status-publish","format-standard","hentry","category-uva","tag-bfs","tag-long-long-int","tag-map","tag-pair","tag-20","tag-22","tag-8","tag-11","tag-9"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts\/607","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=607"}],"version-history":[{"count":4,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts\/607\/revisions"}],"predecessor-version":[{"id":987,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts\/607\/revisions\/987"}],"wp:attachment":[{"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/media?parent=607"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/categories?post=607"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/tags?post=607"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}![\"ZeroJudge](\"https:\/\/seanxd.com\/wp-content\/uploads\/2024\/05\/Walking-on-the-Safe-Side-image-jpeg.webp\")
<\/figure>\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\u6b63\u6574\u6578\uff0c\u4ee3\u8868\u4ee5\u4e0b\u6709\u591a\u5c11\u7d44\u6e2c\u8a66\u8cc7\u6599\u3002
\u6bcf\u7d44\u6e2c\u8a66\u8cc7\u6599\u7684\u7b2c\u4e00\u5217\u6709 2 \u500b\u6574\u6578 W \u548c N (\u5747\u4e0d\u5927\u65bc 100\uff09\uff0cW \u4ee3\u8868\u6771\u897f\u5411\u9053\u8def\u7684\u6578\u76ee\uff0cN \u4ee3\u8868\u5357\u5317\u5411\u9053\u8def\u7684\u6578\u76ee\uff0c\u7de8\u865f\u5982\u4e0a\u5716\u6240\u793a\u3002
\u63a5\u4e0b\u4f86\u7684 W \u5217\u4ee3\u8868\u9019 W \u689d\u6771\u897f\u5411\u9053\u8def\uff0c\u6bcf\u5217\u7684\u7b2c\u4e00\u500b\u6578\u70ba\u9019\u662f\u7b2c\u5e7e\u689d\u6771\u897f\u5411\u9053\u8def\uff0c\u63a5\u4e0b\u4f86\u6709 0 \u500b\u6216\u591a\u500b\u4e0d\u7b49\u7684\u6578<\/strong>\uff0c\u4ee3\u8868\u67d0\u4e9b\u5357\u5317\u5411\u9053\u8def\u8207\u9019\u689d\u6771\u897f\u5411\u9053\u8def\u76f8\u4ea4\u7684\u5341\u5b57\u8def\u53e3\u662f\u5371\u96aa\u7684\u3002
\u8f38\u5165\u7684\u7b2c\u4e00\u5217\u8207\u7b2c\u4e00\u7d44\u6e2c\u8a66\u8cc7\u6599\u4e4b\u9593\uff0c\u4ee5\u53ca\u5404\u7d44\u6e2c\u8a66\u8cc7\u6599\u4e4b\u9593\u5747\u6709\u4e00\u7a7a\u767d\u5217\uff0c\u7b2c\u4e00\u7d44Sample Input \u8868\u793a\u7684\u8def\u5982\u4e0a\u5716\u6240\u793a\uff0c\u8acb\u53c3\u8003\u3002<\/td>\u6bcf\u7d44\u6e2c\u8a66\u8cc7\u6599\u8f38\u51fa\u4e00\u5217\uff0c\u70ba\u4e00\u500b\u6574\u6578\u3002\u4ee3\u8868\u9019\u500b\u4eba\u5f9e\u5de6\u4e0a\u89d2\u8d70\u5230\u53f3\u4e0b\u89d2\u6709\u591a\u5c11\u7a2e\u4e0d\u540c\u7684\u8d70\u6cd5\u3002\u6e2c\u8a66\u8cc7\u6599\u9593\u4ea6\u8acb\u7a7a\u4e00\u5217\u3002<\/td><\/tr> 2
4 5
1
2 2
3 3 5
4
5 5
1
2 1 2 3 4
3 1 2 3
4 1 2 3 5
5 1 2 3<\/td>4
0<\/td><\/tr><\/tbody><\/table>\u89e3\u984c\u601d\u8def<\/h2>\n\n\n\n
\u7bc4\u4f8b\u7a0b\u5f0f\u78bc\uff0dZeroJudge D198: Walking on the Safe Side<\/a><\/h3>\n\n\n\n
#include <iostream>\n#include <vector>\n#include <map>\nusing namespace std;\n\nmap<pair<int, int>, int>MAP;\nvector<vector<long long int>>step;\nint N, M;\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\nvoid BFS(vector<pair<int, int>>start) {\n if (start.size() == 0) return;\n vector<pair<int, int>>newStart;\n map<pair<int, int>, int>appear;\n for (int i = 0; i<start.size(); i++) {\n int y = start[i].first, x = start[i].second;\n if (y == N-1 && x == M-1) return;\n if (y + 1 < N && MAP[axis(y+1, x)] == 0) {\n step[y+1][x] += step[y][x];\n if (appear[axis(y+1, x)] == 0) newStart.push_back(axis(y+1, x));\n appear[axis(y+1, x)]++;\n }\n if (x + 1 < M && MAP[axis(y, x+1)] == 0) {\n step[y][x+1] += step[y][x];\n if (appear[axis(y, x+1)] == 0) newStart.push_back(axis(y, x+1));\n appear[axis(y, x+1)]++;\n }\n }\n BFS(newStart);\n}\n\nint main() {\n cin.sync_with_stdio(0);\n cin.tie(0);\n int T;\n cin >> T;\n for (int i = 0; i<T; i++) {\n MAP.clear();\n step.clear();\n cin >> N >> M;\n string s;\n getline(cin, s);\n for (int j = 0; j<N; j++) {\n string str, tmp;\n vector<int>num;\n getline(cin, str);\n for (int k = 0; k<str.length(); k++) {\n if (str[k] == ' ' && !tmp.empty()) {\n num.push_back(stoi(tmp));\n tmp = "";\n continue;\n }\n tmp += str[k];\n }\n if (!tmp.empty()) num.push_back(stoi(tmp));\n for (int k = 1; k<num.size(); k++) {\n MAP[axis(num[0]-1, num[k]-1)]++;\n }\n vector<long long int>hi;\n for (int k = 0; k<M; k++) hi.push_back(0);\n step.push_back(hi);\n }\n if (MAP[axis(N-1, M-1)] != 0 || MAP[axis(0, 0)] != 0) {\n cout << 0 << "\\n";\n continue;\n }\n vector<pair<int, int>>start;\n start.push_back(axis(0, 0));\n step[0][0] = 1;\n BFS(start);\n cout << step[N-1][M-1] << "\\n";\n }\n}\n\n\/\/ZeroJudge D198\n\/\/Dr. SeanXD<\/code><\/pre><\/div>\n","protected":false},"excerpt":{"rendered":"