{"id":166,"date":"2011-08-22T12:19:34","date_gmt":"2011-08-22T04:19:34","guid":{"rendered":"http:\/\/wangkaixuan.tech\/?p=166"},"modified":"2020-06-04T12:20:07","modified_gmt":"2020-06-04T04:20:07","slug":"zoj-1709-oil-deposits","status":"publish","type":"post","link":"http:\/\/www.wangkaixuan.tech\/?p=166","title":{"rendered":"zoj 1709 Oil Deposits"},"content":{"rendered":"\n<pre class=\"wp-block-code\"><code>\/*\n\u6df1\u641c\u5e94\u7528\n\u904d\u5386\u6bcf\u4e00\u4e2a\n\u7528map\u8bb0\u5f55\u63a2\u6d4b\u51fa\u7684\u6cb9\u4e95\u7684\u4f4d\u7f6e\n\u6ca1\u6709\u63a2\u6d4b\u51fa\u6cb9\u4e95\u7684\u5730\u65b9\u4e3a1\n\u7528DFS\u5bf9\u6bcf\u4e00\u4e2a\u6cb9\u4e95\u8fdb\u884c\u6df1\u641c\n\u76f8\u8fde\u7684\u7684\u6807\u8bb0\u4e3a1\n\u8fd9\u6837\u4e00\u8d9f\u6df1\u641c\u4e0b\u6765\u8fde\u5728\u4e00\u5757\u7684\u6cb9\u4e95\u90fd\u88ab\u6807\u8bb0\u4e3a1\u4e86\n\u7528ans\u8bb0\u5f55\u8fdb\u884c\u7684\u6df1\u641c\u6b21\u6570\u5373\u4e3a\u8981\u6c42\u7684\u6cb9\u4e95\u79cd\u7c7b\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 105\nusing namespace std;\nint m,n;\nint map&#91;N]&#91;N],dir&#91;8]&#91;2]={-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1};\nbool legal(int x,int y)\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 x,int y)\n{\n\tint i,sx,sy;\n\tmap&#91;x]&#91;y]=1;\n\tfor(i=0;i&lt;8;i++)\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])\n\t\t\tDFS(sx,sy);\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\tint ans,i,j;char ch;\n\t   while(cin>>m>>n&amp;&amp;m&amp;&amp;n)\n\t\t{\n\t\t\tmemset(map,0,sizeof(map));\n\t\t\tfor(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=='*')\n\t\t\t\t\t\tmap&#91;i]&#91;j]=1;\n\t\t\t\t}\n\t\t\t}\n\t\t\tans=0;\n\t\t\tfor(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\tif(!map&#91;i]&#91;j])\n\t\t\t\t\t{\n\t\t\t\t\t\tDFS(i,j);\n\t\t\t\t\t\tans++;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t}\n\t\t\tcout&lt;&lt;ans&lt;&lt;endl;\n\t\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-166","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\/166","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=166"}],"version-history":[{"count":0,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/166\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=166"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=166"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=166"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}