{"id":164,"date":"2011-08-22T12:15:25","date_gmt":"2011-08-22T04:15:25","guid":{"rendered":"http:\/\/wangkaixuan.tech\/?p=164"},"modified":"2020-06-04T12:19:26","modified_gmt":"2020-06-04T04:19:26","slug":"zoj-2100-seeding","status":"publish","type":"post","link":"http:\/\/www.wangkaixuan.tech\/?p=164","title":{"rendered":"zoj 2100 Seeding"},"content":{"rendered":"\n<pre class=\"wp-block-code\"><code>\/*\n\u6df1\u641c+\u56de\u6eaf\n\u4ee4\u4eba\u5d29\u6e83\u7684\u56de\u6eaf\u554a\u3002\u3002\u3002\n\u7528\u4e862hours\u5206\u6790\u9012\u5f52\u8fc7\u7a0b\u3002\u3002\u3002\n\u201d\u62d6\u62c9\u673a\u201c\u4e0d\u4f1a\u5206\u8eab\n\u53ea\u6709\u4e00\u6761\u8def\u5f84\u8d70\u5230\u5934\u628a\u6240\u6709\u53ef\u8015\u79cd\u7684\u70b9\u8d70\u5b8c\u624d\u7b97\u662fYES\n\u4e00\u5f00\u59cb\u7406\u89e3\u9519\u4e86\n\u8be6\u89c1\u6ce8\u91ca\u3002\u3002\u3002\n*\/\n#define LOCAL\n#include&lt;cstring>\n#include&lt;string>\n#include&lt;iostream>\nusing namespace std;\nint dir&#91;4]&#91;2]={0,1,0,-1,1,0,-1,0};\/\/\u63a7\u5236\u8f6c\u5411\nint m,n,map&#91;7]&#91;7],yes;\nbool legal(int x,int y)\/\/\u5224\u65ad\u7ed3\u70b9\u662f\u5426\u53ef\u8bbf\u95ee\n{if(x>=1&amp;&amp;x&lt;=m&amp;&amp;y>=1&amp;&amp;y&lt;=n)return true;return false;}\nvoid DFS(int sum,int x,int y)\n{\n\tif(yes) return;\n\tif(sum==m*n) {yes=1;return;}\/\/\u9664\u4e86\u77f3\u5934\u6240\u6709\u90fd\u5df2\u7ecf\u8bbf\u95ee\n\tint sx,sy,i;\n\tfor(i=0;i&lt;4;i++)\/\/\u8f6c\u5411\n\t{\n\t\tsx=x+dir&#91;i]&#91;0];sy=y+dir&#91;i]&#91;1];\n\t\tif(legal(sx,sy)&amp;&amp;!(map&#91;sx]&#91;sy]))\/\/\u82e5\u679c\u8be5\u8282\u70b9\u53ef\u8bbf\u95ee\n\t\t{\n\t\t\tmap&#91;sx]&#91;sy]=1;\/\/\u6807\u8bb0\u5df2\u7ecf\u8bbf\u95ee\n\t\t\tDFS(sum+1,sx,sy);\/\/\u4ece\u5f53\u524d\u8282\u70b9\u5411\u4e0b\u4e00\u7ed3\u70b9\u8fdb\u53d1\n\t\t\tif(yes) return;\n\t\t\tif(map&#91;sx]&#91;sy]==1)\/\/\u6ce8\u610f\u8fd9\u4e2a\u6761\u4ef6\uff0c\u9632\u6b62\u56de\u6eaf\u65f6\u628a\u8bb0\u5f55\u77f3\u5934\u7684\u7ed3\u70b9\u8986\u76d6\u6389\n\t\t\t\tmap&#91;sx]&#91;sy]=0;\n\t\t}\n\t}\n}\nint main()\n{\n#ifdef LOCAL\n       freopen(\"input.txt\",\"r\",stdin);\n       freopen(\"output.txt\",\"w\",stdout);\n#endif\n \n\t   int i,j,nstone;char ch;\n\t   while(cin>>m>>n&amp;&amp;m&amp;&amp;n)\n\t   {\n\t\t   memset(map,0,sizeof(map));\n\t\t   nstone=0;\n\t\t   for(i=1;i&lt;=m;i++)\n\t\t\t{\n\t\t\t\tfor(j=1;j&lt;=n;j++)\n\t\t\t\t{\n\t\t\t\t\tcin>>ch;\n\t\t\t\t\tif(ch=='S'){map&#91;i]&#91;j]=2;nstone++;}\n\t\t\t    }\n\t\t\t}\n\t\t   yes=0;map&#91;1]&#91;1]=1;\/\/\u6807\u8bb0\u51fa\u53d1\u70b9\u5df2\u7ecf\u88ab\u8bbf\u95ee\n\t\t\tDFS(nstone+1,1,1);\/\/\u7528nstone+1\u662f\u56e0\u4e3a\u51fa\u53d1\u70b9\u5df2\u7ecf\u88ab\u8bbf\u95ee\n\t\t\tif(yes){cout&lt;&lt;\"YES\"&lt;&lt;endl;}\n\t\t\telse{cout&lt;&lt;\"NO\"&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-164","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\/164","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=164"}],"version-history":[{"count":0,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/164\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=164"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=164"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=164"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}