{"id":790,"date":"2023-11-01T13:24:06","date_gmt":"2023-11-01T05:24:06","guid":{"rendered":"http:\/\/ggapa.net:81\/?p=790"},"modified":"2023-11-11T23:04:48","modified_gmt":"2023-11-11T15:04:48","slug":"2023-10-30-%e5%ad%a6%e4%b9%a0%e7%ac%94%e8%ae%b0%e9%87%8e%e4%ba%ba%e8%bf%87%e6%b2%b3","status":"publish","type":"post","link":"http:\/\/ggapa.net:81\/2023\/11\/01\/2023-10-30-%e5%ad%a6%e4%b9%a0%e7%ac%94%e8%ae%b0%e9%87%8e%e4%ba%ba%e8%bf%87%e6%b2%b3\/","title":{"rendered":"2023.10.30 \u5b66\u4e60\u7b14\u8bb0(\u91ce\u4eba\u8fc7\u6cb3)"},"content":{"rendered":"<h4>\u9898\u76ee\u63cf\u8ff0<\/h4>\n<p>\u6709\u4e09\u4e2a\u91ce\u4eba\u4e09\u4e2a\u9053\u58eb\uff0c\u4ed6\u4eec\u5728\u4f55\u7684\u53f3\u5cb8\uff0c\u73b0\u6709\u4e00\u8258\u53ea\u80fd\u5bb9\u7eb3\u4e24\u4e2a\u4eba\u7684\u5c0f\u8239\uff0c\u56e0\u4e3a\u91ce\u4eba\u6bd4\u8f83\u91ce\u86ee\uff0c\u5982\u679c\u6cb3\u4e00\u4fa7\u91ce\u4eba\u7684\u6570\u91cf\u5927\u4e8e\u9053\u58eb\u7684\u6570\u91cf\uff0c\u91ce\u4eba\u5c31\u4f1a\u653b\u51fb\u9053\u58eb\uff0c\u95ee\u5982\u4f55\u5b89\u5168\u7684\u8fc7\u6cb3\u3002\u8f93\u51fa\u4efb\u610f\u4e00\u79cd\u65b9\u6848\u3002<\/p>\n<h4>\u95ee\u9898\u5206\u6790<\/h4>\n<p>\u8fd9\u9053\u9898\u76ee\u53ef\u4ee5\u901a\u8fc7\u641c\u7d22\u6765\u5b9e\u73b0\uff0c\u5e7f\u641c\u548c\u6df1\u641c\u5747\u53ef\uff0c\u5728\u8fd9\u91cc\u4e3a\u4e86\u953b\u70bc\u4f7f\u7528\u5e7f\u641c\u7684\u4ee3\u7801\u80fd\u529b\uff0c\u7b14\u8005\u51b3\u5b9a\u7528\u5e7f\u641c\u6765\u89e3\u7b54\u8fd9\u9053\u9898\u76ee\u3002<\/p>\n<p>\u4e3a\u4e86\u8fdb\u884c\u5e7f\u641c\u6211\u4eec\u9700\u8981\u521b\u5efa\u4e00\u4e2a\u4e09\u5143\u7ec4$(x, (y, z))$\uff0c\u5206\u522b\u4ee3\u8868\u7740\u6cb3\u53f3\u5cb8\u9053\u58eb\u7684\u4eba\u6570\uff0c\u91ce\u4eba\u7684\u4eba\u6570\uff0c\u8239\u5728\u5de6\u4fa7\u8fd8\u662f\u5728\u53f3\u4fa7\uff0c\u5176\u4e2d\u8bb0 $1$ \u4e3a\u8239\u5728\u53f3\u4fa7\uff0c\u8bb0 $0$ \u4e3a\u8239\u5728\u5de6\u4fa7\u3002\u5c31\u53ef\u4ee5\u901a\u8fc7\u4e24\u79cd\u60c5\u51b5\u8fdb\u884c\u5206\u7c7b\u8ba8\u8bba\u3002<\/p>\n<p>\u5f53 $z=1$ \u65f6\uff0c\u6709\u4ee5\u4e0b\u51e0\u79cd\u60c5\u51b5\uff1a<\/p>\n<ul>\n<li>\u4e24\u4e2a\u9053\u58eb\u5230\u8fbe\u5de6\u5cb8<\/li>\n<li>\u4e00\u4e2a\u9053\u58eb\u4e00\u4e2a\u91ce\u4eba\u5230\u8fbe\u5de6\u5cb8<\/li>\n<li>\u4e00\u4e2a\u9053\u58eb\u5230\u8fbe\u5de6\u5cb8<\/li>\n<li>\u4e00\u4e2a\u91ce\u4eba\u5230\u8fbe\u5de6\u5cb8<\/li>\n<li>\u4e24\u4e2a\u91ce\u4eba\u5230\u8fbe\u5de6\u5cb8\u3002<\/li>\n<\/ul>\n<p>\u5f53 $z=2$ \u65f6\u7684\u60c5\u51b5\u4e0e\u4e0a\u6587\u76f8\u8fd1\uff0c\u53ea\u662f\u4ece\u5de6\u5cb8\u5230\u8fbe\u53f3\u5cb8\u3002<\/p>\n<p>\u5206\u6790\u5b8c\u6bd5\u540e\uff0c\u6211\u4eec\u53ef\u4ee5\u5f97\u5230\u4ee5\u4e0b\u7684\u8f6c\u79fb\u6570\u7ec4\uff1a<\/p>\n<pre><code class=\"language-cpp\">int dx[10] =  {-1, -1, -2, 0, 0, 1, 1, 2, 0, 0};\nint dy[10] =  {-1, 0, 0, -1, -2, 1, 0, 0, 2, 1};<\/code><\/pre>\n<p>\u5176\u4e2d $0-5$ \u53f7\u5143\u7d20\u4ee3\u8868\u7740\u8239\u5728\u53f3\u5cb8\u7684\u60c5\u51b5\uff0c\u5269\u4f59\u7684\u5143\u7d20\u4ee3\u8868\u8239\u5728\u5de6\u5cb8\u7684\u60c5\u51b5\u3002\u5728\u8f6c\u79fb\u7684\u65f6\u5019\u8981\u5224\u65ad\u72b6\u6001\u7684\u5408\u6cd5\u6027\uff0c\u5207\u8bb0\u5982\u679c\u67d0\u4e00\u65f6\u523b\u9053\u58eb\u7684\u4eba\u6570\u4e3a $0$ \u91ce\u4eba\u662f\u65e0\u6cd5\u653b\u51fb\u9053\u58eb\u7684\u3002<\/p>\n<p>\u56e0\u4e3a\u9898\u76ee\u8981\u6c42\u9700\u8981\u8f93\u51fa\u5408\u6cd5\u7684\u65b9\u6848\uff0c\u6545\u5728\u5e7f\u641c\u7684\u65f6\u5019\u6211\u4eec\u9700\u8981\u901a\u8fc7\u94fe\u8868\u8bb0\u5f55\u4e00\u4e0b\u8fd9\u4e2a\u72b6\u6001\u7684\u4e0a\u4e00\u4e2a\u8f6c\u53f0\uff0c\u6700\u540e\u4ece\u6700\u540e\u7684\u72b6\u6001\u5f00\u59cb\uff0c\u5012\u5e8f\u8f93\u51fa\u3002\u5012\u5e8f\u8f93\u51fa\u53ef\u4ee5\u901a\u8fc7\u6808\u6765\u5b9e\u73b0\uff0c\u8fd9\u91cc\u4e0d\u505a\u8fc7\u591a\u7684\u8bb2\u89e3\u3002<\/p>\n<h4>\u53c2\u8003\u4ee3\u7801<\/h4>\n<pre><code class=\"language-cpp\">#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nint dx[10] =  {-1, -1, -2, 0, 0, 1, 1, 2, 0, 0};\nint dy[10] =  {-1, 0, 0, -1, -2, 1, 0, 0, 2, 1};\nint used[5][5][5];\nint n = 3;\nmap&lt;pair&lt;int, pair&lt;int, int&gt;&gt;, pair&lt;int, pair&lt;int, int&gt;&gt;&gt; ans;\n\nvoid out() {\n    stack&lt;pair&lt;int, pair&lt;int, int&gt;&gt;&gt; tmp;\n    pair&lt;int, pair&lt;int, int&gt;&gt; it =  make_pair(0, make_pair(0, 0)), ed = make_pair(3, make_pair(3, 1));\n    do{\n        tmp.push(it);\n        it = ans[it];\n    }while(it != ed);\n\/\/  cout &lt;&lt; it.first &lt;&lt; &quot; &quot; &lt;&lt; it.second.first &lt;&lt; &quot; &quot; &lt;&lt; it.second.second &lt;&lt; &quot;\\n&quot;;\n    tmp.push(it);\n    while(!tmp.empty()) cout &lt;&lt; tmp.top().first &lt;&lt; &quot; &quot; &lt;&lt; tmp.top().second.first &lt;&lt; &quot; &quot; &lt;&lt; tmp.top().second.second &lt;&lt; &quot;\\n&quot;, tmp.pop();\n    exit(0);\n}\n\nvoid bfs() {\n    queue&lt;pair&lt;int, pair&lt;int, int&gt;&gt;&gt; q;\n\n    q.push(make_pair(3, make_pair(3, 1)));\n    while(!q.empty()) {\n        if(q.front() == make_pair(0, make_pair(0, 0)))  {\n            out();\n            return ;\n        }\n        int x = q.front().first, y = q.front().second.first; \n        if(q.front().second.second) {\n            for(int i = 0; i &lt; 5; i++) {\n                int nx = x + dx[i], ny = y + dy[i];\n                if((nx &lt; ny &amp;&amp; nx != 0) || (n - nx &lt; n - ny &amp;&amp; nx != 3)|| used[nx][ny][0] != 0|| nx &lt; 0 || ny &lt; 0|| nx &gt; n || ny &gt; n) continue;\n                used[nx][ny][0] = 1;\n                q.push(make_pair(nx, make_pair(ny, 0)));\n                ans[make_pair(nx, make_pair(ny, 0))] = make_pair(x, make_pair(y, 1));\n            }\n        }\n        else {\n            for(int i = 5; i &lt; 10; i++) {\n                int nx = x + dx[i], ny = y + dy[i];\n                if((nx &lt; ny &amp;&amp; nx != 0) || (n - nx &lt; n - ny &amp;&amp; nx != 3)||used[nx][ny][1] != 0|| nx &lt; 0 || ny &lt; 0|| nx &gt; n || ny &gt; n) continue;\n                used[nx][ny][1] = 1;\n                q.push(make_pair(nx, make_pair(ny, 1)));\n                ans[make_pair(nx, make_pair(ny, 1))] = make_pair(x, make_pair(y, 0));\n            }\n        }\n        q.pop();\n    }\n} \n\nint main() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n\/\/  freopen(&quot;AKIOI.in&quot;, &quot;r&quot;, stdin);\n\/\/  freopen(&quot;AKIOI.out&quot;, &quot;w&quot;, stdout);\n    bfs();\n    return 0;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u63cf\u8ff0 \u6709\u4e09\u4e2a\u91ce\u4eba\u4e09\u4e2a\u9053\u58eb\uff0c\u4ed6\u4eec\u5728\u4f55\u7684\u53f3\u5cb8\uff0c\u73b0\u6709\u4e00\u8258\u53ea\u80fd\u5bb9\u7eb3\u4e24\u4e2a\u4eba\u7684\u5c0f\u8239\uff0c\u56e0\u4e3a\u91ce\u4eba\u6bd4\u8f83\u91ce\u86ee\uff0c\u5982\u679c\u6cb3\u4e00\u4fa7\u91ce\u4eba\u7684 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[30],"_links":{"self":[{"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/posts\/790"}],"collection":[{"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/comments?post=790"}],"version-history":[{"count":5,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/posts\/790\/revisions"}],"predecessor-version":[{"id":795,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/posts\/790\/revisions\/795"}],"wp:attachment":[{"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/media?parent=790"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/categories?post=790"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/ggapa.net:81\/wp-json\/wp\/v2\/tags?post=790"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}