{"id":223,"date":"2011-11-25T12:33:50","date_gmt":"2011-11-25T04:33:50","guid":{"rendered":"http:\/\/ykyi.net\/?p=223"},"modified":"2011-11-25T12:33:50","modified_gmt":"2011-11-25T04:33:50","slug":"acm-%e9%a9%ac%e5%91%a8%e6%b8%b8%e8%a7%a3%e9%a2%98%e6%8a%a5%e5%91%8a","status":"publish","type":"post","link":"https:\/\/ykyi.net\/?p=223","title":{"rendered":"ACM \u9a6c\u5468\u6e38\u89e3\u9898\u62a5\u544a"},"content":{"rendered":"
\n\t
<\/p>\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

\u7b80\u5355\u7684\u9a6c\u5468\u6e38\u95ee\u9898<\/span><\/h3>\n

 <\/p>\n

 <\/p>\n

\t<\/center>\n<\/div>\n

 <\/p>\n

 <\/div>\n
Description<\/span><\/div>\n
 <\/div>\n
\u5728\u4e00\u4e2a5 * 6\u7684\u68cb\u76d8\u4e2d\u7684\u67d0\u4e2a\u4f4d\u7f6e\u6709\u4e00\u53ea\u9a6c\uff0c\u5982\u679c\u5b83\u8d7029\u6b65\u6b63\u597d\u7ecf\u8fc7\u9664\u8d77\u70b9\u5916\u7684\u5176\u4ed6\u4f4d\u7f6e\u5404\u4e00\u6b21\uff0c\u8fd9\u6837\u4e00\u79cd\u8d70\u6cd5\u5219\u79f0\u9a6c\u7684\u5468\u6e38\u8def\u7ebf\uff0c\u8bd5\u8bbe\u8ba1\u4e00\u4e2a\u7b97\u6cd5\uff0c\u4ece\u7ed9\u5b9a\u7684\u8d77\u70b9\u51fa\u53d1\uff0c\u627e\u51fa\u5b83\u7684\u4e00\u6761\u5468\u6e38\u8def\u7ebf\u3002<\/span><\/div>\n
 <\/div>\n
\u4e3a\u4e86\u4fbf\u4e8e\u8868\u793a\u4e00\u4e2a\u68cb\u76d8\uff0c\u6211\u4eec\u6309\u7167\u4ece\u4e0a\u5230\u4e0b\uff0c\u4ece\u5de6\u5230\u53f3\u5bf9\u68cb\u76d8\u7684\u65b9\u683c\u7f16\u53f7\uff0c\u5982\u4e0b\u6240\u793a\uff1a<\/span><\/div>\n
 <\/div>\n
1     2     3       4     5     6<\/span><\/div>\n
 <\/div>\n
7     8     9       10    11       12<\/span><\/div>\n
 <\/div>\n
13    14       15    16       17    18<\/span><\/div>\n
 <\/div>\n
19    20       21    22       23    24<\/span><\/div>\n
 <\/div>\n
25    26       27    28       29    30<\/span><\/div>\n
 <\/div>\n
\u9a6c\u7684\u8d70\u6cd5\u662f“\u65e5”\u5b57\u5f62\u8def\u7ebf\uff0c\u4f8b\u5982\u5f53\u9a6c\u5728\u4f4d\u7f6e15\u7684\u65f6\u5019\uff0c\u5b83\u53ef\u4ee5\u5230\u8fbe2\u30014\u30017\u300111\u300119\u300123\u300126\u548c28\u3002\u4f46\u662f\u89c4\u5b9a\u9a6c\u662f\u4e0d\u80fd\u8df3\u51fa\u68cb\u76d8\u5916\u7684\uff0c\u4f8b\u5982\u4ece\u4f4d\u7f6e1\u53ea\u80fd\u5230\u8fbe9\u548c14\u3002<\/span><\/div>\n
 <\/div>\n
Input<\/span><\/div>\n
 <\/div>\n
\u8f93\u5165\u6709\u82e5\u5e72\u884c\u3002\u6bcf\u884c\u4e00\u4e2a\u6574\u6570N(1<=N<=30)\uff0c\u8868\u793a\u9a6c\u7684\u8d77\u70b9\u3002\u6700\u540e\u4e00\u884c\u7528-1\u8868\u793a\u7ed3\u675f\uff0c\u4e0d\u7528\u5904\u7406\u3002<\/span><\/div>\n
 <\/div>\n
Output<\/span><\/div>\n
 <\/div>\n
\u5bf9\u8f93\u5165\u7684\u6bcf\u4e00\u4e2a\u8d77\u70b9\uff0c\u6c42\u4e00\u6761\u5468\u6e38\u7ebf\u8def\u3002\u5bf9\u5e94\u5730\u8f93\u51fa\u4e00\u884c\uff0c\u670930\u4e2a\u6574\u6570\uff0c\u4ece\u8d77\u70b9\u5f00\u59cb\u6309\u987a\u5e8f\u7ed9\u51fa\u9a6c\u6bcf\u6b21\u7ecf\u8fc7\u7684\u68cb\u76d8\u65b9\u683c\u7684\u7f16\u53f7\u3002\u76f8\u90bb\u7684\u6570\u5b57\u7528\u4e00\u4e2a\u7a7a\u683c\u5206\u5f00\u3002<\/span><\/div>\n
 <\/div>\n
Sample Input<\/span><\/div>\n
 <\/div>\n
4<\/span><\/div>\n
-1<\/span><\/div>\n
Sample Output<\/span><\/div>\n
 <\/div>\n
\u6ce8\u610f\uff1a\u5982\u679c\u8d77\u70b9\u548c\u8f93\u5165\u7ed9\u5b9a\u7684\u4e0d\u540c\uff0c\u91cd\u590d\u591a\u6b21\u7ecf\u8fc7\u540c\u4e00\u65b9\u683c\u6216\u8005\u6709\u7684\u65b9\u683c\u6ca1\u6709\u88ab\u7ecf\u8fc7\uff0c\u90fd\u4f1a\u88ab\u8ba4\u4e3a\u662f\u9519\u8bef\u7684\u3002<\/span><\/div>\n
 <\/div>\n
 <\/div>\n
\uff081\uff09\u539f\u9898\u4e2d\u6587\u5927\u610f<\/span><\/div>\n
 <\/div>\n
\u4e2d\u56fd\u8c61\u68cb\u7684\u9a6c\u6309\u7167\u8c61\u68cb\u7684\u89c4\u5219\u57285 x 6 \u7684\u68cb\u76d8\u4e0a\u8dd130\u6b65\u8dd1\u5b8c\u6240\u6709\u7684\u683c\u5b50\u3002<\/span><\/div>\n
 <\/div>\n
 <\/div>\n
 <\/div>\n
\uff082\uff09\u7b97\u6cd5\u601d\u60f3\u53ca\u89e3\u9898\u7528\u5230\u7684\u4e3b\u8981\u6570\u636e\u7ed3\u6784<\/span><\/div>\n
 <\/div>\n
 <\/div>\n
 <\/div>\n
\u4ece\u6bcf\u4e00\u4e2a\u70b9\u5f80\u4e0b\u8d70\u7b2c\u4e8c\u6b65\uff0c\u4f1a\u6709\u51e0\u70b9\u6709\u6548\u7684\u884c\u8d70\u4f4d\u7f6e\u3002 \u628a\u5f53\u524d\u4f4d\u7f6e\u8bb0\u5728\u6808\u91cc\u9762\uff0c\u4ee5\u6df1\u5ea6\u4f18\u5148\u7684\u65b9\u5f0f\u8fdb\u5165\u4e0b\u4e00\u4e2a\u6709\u6548\u4f4d\u7f6e\u3002\u5982\u679c\u4e0b\u4e00\u4e2a\u6709\u6548\u4f4d\u7f6e\u5728\u4e4b\u524d\u5df2\u7ecf\u8d70\u8fc7\uff0c\u5219\u4ece\u6808\u9876\u5f39\u51fa\u4e0a\u4e00\u4f4d\u7f6e\uff0c\u6062\u590d\u5230\u8c03\u51fa\u7684\u4f4d\u7f6e\u540e\u5c1d\u8bd5\u672a\u8d70\u8fc7\u7684\u6709\u6548\u4f4d\u7f6e\u3002\u5229\u7528\u51fd\u6570\u8c03\u7528\u65f6\u4f1a\u538b\u6808\u7684\u7279\u522b\uff0c\u7528\u51fd\u6570\u9012\u5f52\u8c03\u7528\u5373\u53ef\u89e3\u51b3\u95ee\u9898\u3002<\/span><\/div>\n
 <\/div>\n
 <\/div>\n
 <\/div>\n
\uff083\uff09\u8be6\u7ec6\u89e3\u9898\u601d\u8def<\/span><\/div>\n
 <\/div>\n
1. \u5148\u521d\u59cb\u5316\u4e00\u5f20\u8868\u3002\u8fd9\u5f20\u8868\u8bb0\u4e0b\u4e86\u68cb\u76d8\u4e0a\u6240\u6709\u768430\u4e2a\u4f4d\u7f6e\u7684\u4e0b\u4e00\u6b65\u53ef\u8d70\u7684\u6709\u6548\u4f4d\u7f6e.<\/span><\/div>\n
 <\/div>\n
2. \u5199\u4e00\u4e2a\u4e00\u822c\u7684\u9012\u5f52\u8c03\u7528\u81ea\u5df1\u7684\u51fd\u6570\uff0c\u8868\u793a\u9a6c\u5728\u8d70\u7b2c\u51e0\u6b65\u65f6\u5230\u4e86\u54ea\u4e2a\u4f4d\u7f6e\uff0c\u7136\u540e\u5c1d\u8bd5\u8d70\u4f59\u4e0b\u7684\u6240\u6709\u53ef\u8d70\u4f4d\u7f6e\u3002<\/span><\/div>\n
 <\/div>\n
3. \u9012\u5f52\u51fd\u6570\u6709\u4e24\u4e2a\u9000\u51fa\u6761\u4ef6\u3002\u8981\u4e48\u4e0b\u4e00\u4e2a\u8981\u5c1d\u8bd5\u7684\u70b9\u5df2\u7ecf\u8d70\u8fc7\u4e86\uff0c\u8981\u4e48\u8d70\u5230\u4e86\u6700\u540e\u4e00\u6b65\uff0c\u5373\u5f97\u89e3\uff01<\/span><\/div>\n
 <\/div>\n
 <\/div>\n
 <\/div>\n
\uff084\uff09\u9010\u6b65\u6c42\u7cbe\u7b97\u6cd5\u63cf\u8ff0<\/span><\/div>\n
 <\/div>\n
\u7528\u4e00\u4e2a\u6570\u7ec4\u8bb0\u4e0b\u6765\u7ecf\u8fc7\u7684\u70b9\u3002<\/span><\/div>\n
 <\/div>\n
 <\/div>\n
 <\/div>\n
\uff085\uff09\u7a0b\u5e8f\u6ce8\u91ca\u6e05\u5355<\/span><\/div>\n
 <\/div>\n
\n
#include <iostream>\n\n#include <cstring>\n\n#include <cstdlib>\n\n#include <vector>\n\nusing namespace std;\n\nconst static char row_num = 5;   \/\/ 5\u884c\n\nconst static char column_num = 6;  \/\/ 6\u5217\n\n\n\n\/\/ \u8fd9\u4e2a\u5168\u5c40\u6570\u7ec4\u5728\u521d\u59cb\u5316\u540e\u4f1a\u8bb0\u4e0b\u6bcf30\u4e2a\u6709\u6548\u4f4d\u7f6e\u7684\u4e0b\u4e00\u6b65\u53ef\u8d70\u4f4d\u7f6e.\n\n\/\/ elocution[x][0]\u8bb0\u4e2a\u6570\u3002\u6700\u591a8\u4e2a\u6709\u6548\u53ef\u8d70\u4f4d\u7f6e\u3002\n\nchar elocution[30][9];\n\nstruct coordinate  \/\/ \u5750\u6807.\n\n{\n\nchar _x;  \/\/ start from zero.\n\nchar _y;\n\n};\n\n\/\/ \u5750\u6807\u8f6c\u5e8f\u53f7\u7684\u51fd\u6570\u3002\n\nchar coordinate2serial_num(coordinate co)\n\n{\n\nchar num = co._x * column_num + co._y + 1;\n\nreturn num;\n\n}\n\n\/\/ \u5e8f\u53f7\u8f6c\u5750\u6807\u7684\u51fd\u6570\u3002\n\ncoordinate serial_num2coordinate(char sn)\n\n{\n\ncoordinate co;\n\nco._x = (sn - 1) \/ column_num;\n\nco._y = sn - co._x * column_num - 1;\n\nreturn co;\n\n}\n\n\/\/ \u589e\u91cf\u6570\u7ec4.\n\nchar increments[8][2] =\n\n{\n\n1, -2, 2, -1, 2, 1, 1, 2,\n\n-1, 2, -2, 1, -2, -1, -1, -2\n\n};\n\n\/\/ \u5f97\u7528\u589e\u91cf\u6570\u7ec4\u6765\u8ba1\u7b97\u6bcf\u4e00\u4e2a\u4f4d\u7f6e\u7684\u4e0b\u4e00\u6b65\u6709\u6548\u4f4d\u7f6e\u3002\u8bb0\u5230steps\u91cc\u9762.\n\nvoid next_step(char pos, char steps[])\n\n{\n\nchar valid_count = 0;\n\ncoordinate co = serial_num2coordinate(pos);\n\ncoordinate tmp;\n\nchar serial_num;\n\nfor ( int i = 0; i < 8; i++ )\n\n{\n\ntmp._x = co._x + increments[i][0];\n\ntmp._y = co._y + increments[i][1];\n\nif ( tmp._x < 0 || tmp._x > 4 || tmp._y < 0 || tmp._y > 5 )\n\n{\n\ncontinue;\n\n}\n\nserial_num = coordinate2serial_num(tmp);\n\nif ( serial_num >= 1 && serial_num <= 30 )\n\n{\n\nvalid_count++;\n\nsteps[valid_count] = serial_num;\n\n}\n\nelse\n\n{\n\ncerr << "Not expected to reach here.\\n";\n\n}\n\n}\n\nsteps[0] = valid_count;\n\n}\n\n\/\/ \u521d\u59cb\u5316\u8bb0\u8f7d\u6240\u6709\u70b9\u7684\u4e0b\u4e00\u6b65\u53ef\u8d70\u70b9\u7684\u5168\u5c40\u8868\u3002\n\nvoid init_elocution()\n\n{\n\nfor ( int i = 1; i <= 30; i++ )\n\n{\n\nnext_step(i, elocution[i-1]);\n\n}\n\n}\n\n\n\nchar track[30];   \/\/ \u8bb0\u8d70\u8fc7\u7684\u8def\u5f84.\n\nbool quit_run_horse;\n\n\/\/ \u4e0a\u6587\u63d0\u9ad8\u7684\u9012\u5f52\u51fd\u7528\u51fd\u6570.\n\nvoid run_horse(char start_pos, char step_count)\n\n{\n\nif ( quit_run_horse ) \/\/ \u7528\u6765\u5feb\u901f\u9000\u51fa\u6df1\u5d4c\u5957\u9012\u5f52\u8c03\u7528\u51fd\u6570.\n\n{\n\nreturn;\n\n}\n\nfor ( int i = 0; i < step_count; i++ )\n\n{\n\n\/\/ \u5df2?\u7ecf-\u7ecf-\u8fc7y\u8fd9a\u70b9?\u4e86?.\n\nif ( track[i] == start_pos )\n\n{\n\nreturn;\n\n}\n\n}\n\ntrack[step_count] = start_pos; \/\/ \u8bb0\u4e0b\u65b0\u8d70\u8fc7\u7684\u4f4d\u7f6e\n\n\n\nif ( step_count == 29 )  \/\/ \u6700\u540e\u4e00\u6b65\u5219\u6253\u5370\u51fa\u7ed3\u679c\u3002\n\n{\n\nfor ( int i = 0; i < sizeof(track); i++ )\n\n{\n\ncout << (int)track[i];\n\nif ( i + 1 != sizeof(track) )\n\n{\n\ncout << " ";\n\n}\n\n}\n\ncout << endl;\n\nquit_run_horse = true;\n\nreturn;\n\n}\n\n\n\nfor ( int i = 0; i < elocution[start_pos-1][0]; i++ )\n\n{\n\nrun_horse(elocution[start_pos-1][i+1], step_count+1);\n\n}\n\n}\n\nint main(int argc, char* argv[])\n\n{\n\ninit_elocution();\n\nint pos;\n\nvector<int> vec;\n\n\n\nwhile(true)\n\n{\n\ncin >> pos;\n\nif (pos==-1)\n\n{\n\nbreak;\n\n}\n\nvec.push_back(pos);\n\n}\n\n\n\nfor ( int i = 0; i < vec.size(); i++ )\n\n{\n\nquit_run_horse = false;\n\nrun_horse(vec[i], 0);\n\n}\n\nreturn 0;\n\n}\n<\/pre>\n
 <\/p>\n<\/div>\n
 <\/div>\n
 <\/div>\n
 <\/div>\n","protected":false},"excerpt":{"rendered":"
      \u7b80\u5355\u7684\u9a6c\u5468\u6e38\u95ee\u9898         Description   \u5728\u4e00\u4e2a5 * 6\u7684\u68cb\u76d8\u4e2d\u7684\u67d0\u4e2a\u4f4d\u7f6e\u6709\u4e00\u53ea\u9a6c\uff0c\u5982\u679c\u5b83\u8d7029\u6b65\u6b63\u597d\u7ecf\u8fc7\u9664\u8d77\u70b9\u5916\u7684\u5176\u4ed6\u4f4d\u7f6e\u5404\u4e00\u6b21\uff0c\u8fd9\u6837\u4e00\u79cd\u8d70\u6cd5\u5219\u79f0\u9a6c\u7684\u5468\u6e38\u8def\u7ebf\uff0c\u8bd5\u8bbe\u8ba1\u4e00\u4e2a\u7b97\u6cd5\uff0c\u4ece\u7ed9\u5b9a\u7684\u8d77\u70b9\u51fa\u53d1\uff0c\u627e\u51fa\u5b83\u7684\u4e00\u6761\u5468\u6e38\u8def\u7ebf\u3002   \u4e3a\u4e86\u4fbf\u4e8e\u8868\u793a\u4e00\u4e2a\u68cb\u76d8\uff0c\u6211\u4eec\u6309\u7167\u4ece\u4e0a\u5230\u4e0b\uff0c\u4ece\u5de6\u5230\u53f3\u5bf9\u68cb\u76d8\u7684\u65b9\u683c\u7f16\u53f7\uff0c\u5982\u4e0b\u6240\u793a\uff1a   1     2     3       4     5     6   7     8     9       10    11       12   13    14 … Continue reading “ACM \u9a6c\u5468\u6e38\u89e3\u9898\u62a5\u544a”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[14],"class_list":["post-223","post","type-post","status-publish","format-standard","hentry","category-tech_articles","tag-acm"],"_links":{"self":[{"href":"https:\/\/ykyi.net\/index.php?rest_route=\/wp\/v2\/posts\/223","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ykyi.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/ykyi.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/ykyi.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/ykyi.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=223"}],"version-history":[{"count":0,"href":"https:\/\/ykyi.net\/index.php?rest_route=\/wp\/v2\/posts\/223\/revisions"}],"wp:attachment":[{"href":"https:\/\/ykyi.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=223"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/ykyi.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=223"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/ykyi.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=223"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}