{"id":132,"date":"2011-08-20T23:18:39","date_gmt":"2011-08-20T15:18:39","guid":{"rendered":"http:\/\/wangkaixuan.tech\/?p=132"},"modified":"2020-06-03T23:19:36","modified_gmt":"2020-06-03T15:19:36","slug":"zoj-1940-dungeon-master","status":"publish","type":"post","link":"http:\/\/www.wangkaixuan.tech\/?p=132","title":{"rendered":"zoj 1940 Dungeon Master"},"content":{"rendered":"\n<pre class=\"wp-block-code\"><code>\/*\n\u4e09\u7ef4\u5e7f\u641c\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>\n#define N 30\nusing namespace std;\nclass POSITION \n{public:int x,y,z;};\nint map&#91;N+5]&#91;N+5]&#91;N+5],l,r,c,dir&#91;6]&#91;3]={0,0,1,0,0,-1,0,1,0,0,-1,0,1,0,0,-1,0,0};\nbool legal(POSITION po)\n{if(po.x>=1&amp;&amp;po.x&lt;=l&amp;&amp;po.y>=1&amp;&amp;po.y&lt;=r&amp;&amp;po.z>=1&amp;&amp;po.z&lt;=c) 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   int ex,ey,ez,i,j,k;POSITION po,pos;char ch;\n\t   while(cin>>l>>r>>c&amp;&amp;l)\n\t   {\n\t\t   memset(map,-1,sizeof(map));\n\t\t   queue&lt;POSITION>q;\n\t\t\tfor(i=1;i&lt;=l;i++)\n\t\t\t{\n\t\t\t\tfor(j=1;j&lt;=r;j++)\n\t\t\t\t{\n\t\t\t\t\tfor(k=1;k&lt;=c;k++)\n\t\t\t\t\t{\n\t\t\t\t\t\tcin>>ch;\n\t\t\t\t\t\tif(ch=='#') map&#91;i]&#91;j]&#91;k]=1;\n\t\t\t\t\t\telse if(ch=='S'){pos.x=i;pos.y=j;pos.z=k;map&#91;i]&#91;j]&#91;k]=0;q.push(pos);}\n\t\t\t\t\t\telse if(ch=='E'){ex=i;ey=j;ez=k;}\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t}\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;6;i++)\n\t\t\t\t{\n\t\t\t\t\tpos.x=po.x+dir&#91;i]&#91;0];pos.y=po.y+dir&#91;i]&#91;1];pos.z=po.z+dir&#91;i]&#91;2];\n\t\t\t\t\tif(legal(pos)&amp;&amp;map&#91;pos.x]&#91;pos.y]&#91;pos.z]==-1){map&#91;pos.x]&#91;pos.y]&#91;pos.z]=map&#91;po.x]&#91;po.y]&#91;po.z]+1;q.push(pos);}\n\t\t\t\t}\n\t\t\t}\n\t\t\tif(map&#91;ex]&#91;ey]&#91;ez]!=-1)cout&lt;&lt;\"Escaped in \"&lt;&lt;map&#91;ex]&#91;ey]&#91;ez]&lt;&lt;\" minute(s).\"&lt;&lt;endl;\n\t\t\telse cout&lt;&lt;\"Trapped!\"&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-132","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\/132","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=132"}],"version-history":[{"count":0,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/132\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=132"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=132"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=132"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}