{"id":130,"date":"2011-08-19T23:17:15","date_gmt":"2011-08-19T15:17:15","guid":{"rendered":"http:\/\/wangkaixuan.tech\/?p=130"},"modified":"2020-06-03T23:17:51","modified_gmt":"2020-06-03T15:17:51","slug":"zoj-1091-knight-moves","status":"publish","type":"post","link":"http:\/\/www.wangkaixuan.tech\/?p=130","title":{"rendered":"zoj 1091 Knight Moves"},"content":{"rendered":"\n<pre class=\"wp-block-code\"><code>\/*\n\u7ee7\u7eed\u5e7f\u641c\n\u4e00\u6b21AC\n\u5475\u5475\u3002\u3002\u3002\n*\/\n#define LOCAL\n#include&lt;iostream>\n#include&lt;cstdio>\n#include&lt;cmath>\n#include&lt;cstring>\n#include&lt;cstdlib>\n#include&lt;cctype>\n#include&lt;iomanip>\n#include&lt;string>\n#include&lt;algorithm>\n#include&lt;ctime>\n#include&lt;stack>\n#include&lt;queue>\n#include&lt;vector>\nclass Cordinate\n{public:int x,y;};\nusing namespace std;\nint dir&#91;8]&#91;2]={1,2,1,-2,2,1,2,-1,-1,2,-1,-2,-2,1,-2,-1},chess&#91;10]&#91;10];\nbool legal(Cordinate po)\n{if(po.x>=1&amp;&amp;po.x&lt;=8&amp;&amp;po.y>=1&amp;&amp;po.y&lt;=8)return true;return false;}\nint main()\n{\n#ifdef LOCAL\n       freopen(\"input.txt\",\"r\",stdin);\n       freopen(\"output.txt\",\"w\",stdout);\n#endif\n \n\t   char a&#91;3],b&#91;3];Cordinate po,pos;int i;\n\t   while(cin>>a>>b)\n\t   {\n\t\t    queue&lt;Cordinate>q;\n\t\t    memset(chess,-1,sizeof(chess));\n\t\t    pos.x=a&#91;0]-'a'+1;pos.y=a&#91;1]-'0';\n\t\t\tchess&#91;pos.x]&#91;pos.y]=0;\n\t\t\tq.push(pos);\n\t\t\twhile(!q.empty())\n\t\t\t{\n\t\t\t\tpo=q.front();q.pop();\n\t\t\t\tfor(i=0;i&lt;8;i++)\n\t\t\t\t{\n\t\t\t\t\tpos.x=dir&#91;i]&#91;0]+po.x;pos.y=dir&#91;i]&#91;1]+po.y;\n\t\t\t\t\tif(legal(pos)&amp;&amp;chess&#91;pos.x]&#91;pos.y]==-1) {q.push(pos);chess&#91;pos.x]&#91;pos.y]=chess&#91;po.x]&#91;po.y]+1;}\n\t\t\t\t}\n\t\t\t}\n\t\t\tcout&lt;&lt;\"To get from \"&lt;&lt;a&lt;&lt;\" to \"&lt;&lt;b&lt;&lt;\" takes \"&lt;&lt;chess&#91;b&#91;0]-'a'+1]&#91;b&#91;1]-'0']&lt;&lt;\" knight moves.\"&lt;&lt;endl;\n\t   }\n\t\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[],"class_list":["post-130","post","type-post","status-publish","format-standard","hentry","category-06-01-acm"],"_links":{"self":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/130","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=130"}],"version-history":[{"count":0,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/130\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=130"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=130"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=130"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}