{"id":317,"date":"2019-10-04T17:35:20","date_gmt":"2019-10-04T09:35:20","guid":{"rendered":"http:\/\/www.guanhaobo.cn\/?p=317"},"modified":"2019-10-04T17:35:20","modified_gmt":"2019-10-04T09:35:20","slug":"poj-2386-lake-counting","status":"publish","type":"post","link":"https:\/\/www.guanhaobo.cn\/?p=317","title":{"rendered":"POJ 2386 \u2014 Lake Counting"},"content":{"rendered":"<h3>Description<\/h3>\n<p>Due to recent rains, water has pooled in various places in Farmer John&#8217;s field, which is represented by a rectangle of N x M (1 &lt;= N &lt;= 100; 1 &lt;= M &lt;= 100) squares. Each square contains either water (&#8216;W&#8217;) or dry land (&#8216;.&#8217;). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors.<\/p>\n<p>Given a diagram of Farmer John&#8217;s field, determine how many ponds he has.<\/p>\n<h3>Input<\/h3>\n<ul>\n<li>Line 1: Two space-separated integers: N and M<\/p>\n<\/li>\n<li>\n<p>Lines 2..N+1: M characters per line representing one row of Farmer John&#8217;s field. Each character is either &#8216;W&#8217; or &#8216;.&#8217;. The characters do not have spaces between them.<\/p>\n<\/li>\n<\/ul>\n<h3>Output<\/h3>\n<ul>\n<li>Line 1: The number of ponds in Farmer John&#8217;s field.<\/li>\n<\/ul>\n<h3>Sample Input<\/h3>\n<pre><code class=\"language-cpp line-numbers\">10 12\nW........WW.\n.WWW.....WWW\n....WW...WW.\n.........WW.\n.........W..\n..W......W..\n.W.W.....WW.\nW.W.W.....W.\n.W.W......W.\n..W.......W.\n<\/code><\/pre>\n<h3>Sample Output<\/h3>\n<p><code>3<\/code><\/p>\n<h3>Hint<\/h3>\n<p>OUTPUT DETAILS:<br \/>\nThere are three ponds: one in the upper left, one in the lower left,and one along the right side.<\/p>\n<h3>\u9898\u76ee\u94fe\u63a5<\/h3>\n<p><a href=\"http:\/\/poj.org\/problem?id=2386\" title=\"http:\/\/poj.org\/problem?id=2386\">http:\/\/poj.org\/problem?id=2386<\/a><\/p>\n<h3>\u9898\u76ee\u7ffb\u8bd1<\/h3>\n<p>\u6709\u4e00\u4e2a\u5927\u5c0f\u4e3a N\u00d7M \u7684\u56ed\u5b50\uff0c\u96e8\u540e\u79ef\u8d77\u4e86\u6c34\u3002\u516b\u8fde\u901a\u7684\u79ef\u6c34\u88ab\u8ba4\u4e3a\u662f\u8fde\u901a\u5728\u4e00\u8d77\u7684\uff08W\u8868\u793a\u79ef\u6c34\uff0c\u79ef\u6c34\u7684\u4e0a\u4e0b\u5de6\u53f3\u548c\u5de6\u4e0a\u53f3\u4e0a\u5de6\u4e0b\u53f3\u4e0b\u8fd9\u516b\u4e2a\u65b9\u5411\u5982\u679c\u6709\u79ef\u6c34\uff0c\u5219\u8ba4\u4e3a\u5b83\u4eec\u662f\u8fde\u901a\u7684\uff09\u3002\u8bf7\u6c42\u51fa\u56ed\u5b50\u91cc\u603b\u5171\u6709\u591a\u5c11\u6c34\u6d3c\uff1f<br \/>\nN\uff0cM&lt;=100<\/p>\n<h3>\u9898\u76ee\u5206\u6790<\/h3>\n<p>\u6df1\u5ea6\u4f18\u5148\u641c\u7d22\u5373\u53ef\u3002<br \/>\n\u904d\u5386\u6bcf\u4e00\u4e2a\u70b9\uff0c\u5982\u679c\u503c\u4e3aW\uff0c\u5219\u4ee5\u8fd9\u4e2a\u70b9\u4e3a\u8d77\u70b9\u5f00\u59cb\u6df1\u641c\uff0c\u7b54\u6848 ans++\u3002<br \/>\n\u5728\u6df1\u641c\u7684\u8fc7\u7a0b\u4e2d\uff0c\u9996\u5148\u5c06\u5f53\u524d\u70b9\u7684\u503c\u66f4\u6539\u4e3a<code>.<\/code>\uff0c\u7136\u540e\u904d\u5386\u5f53\u524d\u70b9\u7684\u516b\u4e2a\u65b9\u5411\u4e0a\u7684\u70b9\uff0c\u5982\u679c\u503c\u4e3aW\uff0c\u5219\u4ee5\u5176\u4e3a\u8d77\u70b9\u8fdb\u884c\u6df1\u641c\u3002<br \/>\n\u5177\u4f53\u770b\u4ee3\u7801\u5427\u3002<\/p>\n<h3>AC\u4ee3\u7801<\/h3>\n<pre><code class=\"language-cpp line-numbers\">#include &lt;iostream&gt;\nusing namespace std;\n\nint n, m;\nchar num[105][105];\n\nvoid dfs(int x, int y)\n{\n    num[x][y] = '.';\n    int d[] = {0, -1, 1}, i, j;\n    for (i = 0; i &lt; 3; i++)\n    {\n        for (j = 0; j &lt; 3; j++)\n        {\n            int x1 = x + d[i], y1 = y + d[j];\n            if (x1 &lt; n &amp;&amp; x1 &gt;= 0 &amp;&amp; y1 &lt; m &amp;&amp; y1 &gt;= 0 &amp;&amp; num[x1][y1] == 'W')\n            {\n                dfs(x1, y1);\n            }\n        }\n    }\n}\n\nint main()\n{\n    int i, j, ans = 0;\n    cin &gt;&gt; n &gt;&gt; m;\n    for (i = 0; i &lt; n; i++)\n        cin &gt;&gt; num[i];\n    for (i = 0; i &lt; n; i++)\n    {\n        for (j = 0; j &lt; m; j++)\n        {\n            if (num[i][j] == 'W')\n            {\n                dfs(i, j);\n                ans++;\n            }\n        }\n    }\n    cout &lt;&lt; ans &lt;&lt; endl;\n    return 0;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Description Due to recent rains, water has pooled in va [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[11,25],"class_list":["post-317","post","type-post","status-publish","format-standard","hentry","category-algo","tag-dfs","tag-poj"],"_links":{"self":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/317","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=317"}],"version-history":[{"count":0,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/317\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=317"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=317"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=317"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}