{"id":2545,"date":"2018-04-29T16:29:21","date_gmt":"2018-04-29T08:29:21","guid":{"rendered":"https:\/\/boweihe.me\/?p=2545"},"modified":"2018-04-29T16:29:21","modified_gmt":"2018-04-29T08:29:21","slug":"leetcode-200-number-of-islands","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=2545","title":{"rendered":"LeetCode 200. Number of Islands"},"content":{"rendered":"<p>https:\/\/leetcode.com\/problems\/number-of-islands\/description\/<br \/>\nDFS of a map, O(N^2)<\/p>\n<pre class=\"theme:github lang:c++ decode:true \">class Solution {\npublic:\n    bool visit(vector&lt;vector&lt;char&gt;&gt;&amp; grid, int row, int col)\n    {\n        \/\/ if has any island, return true\n        \/\/ DFS on grid\n        const int rows = grid.size();\n        if (rows == 0 || row &gt;= rows || row &lt; 0)\n            return false;\n        const int cols = grid[0].size();\n        if (cols == 0 || col &gt;= cols || col &lt; 0)\n            return false;\n        if (grid[row][col] == 'V')\n            return false;\n        else if (grid[row][col] == '0')\n            return false;\n        grid[row][col] = 'V';\n        visit(grid, row, col-1);\n        visit(grid, row-1, col);\n        visit(grid, row+1, col);\n        visit(grid, row, col+1);\n        return true;\n    }\n    int numIslands(vector&lt;vector&lt;char&gt;&gt;&amp; grid) {\n        \/\/ mark visited as 'V'\n        int result = 0;\n        for (int row = 0; row &lt; grid.size(); ++row)\n        {\n            for (int col = 0; col &lt; grid[0].size(); ++col)\n            {\n                if (grid[row][col] == 'V' || grid[row][col] == '0')\n                {\n                    continue;\n                }\n                if (visit(grid, row, col))\n                    result++;\n            }\n        }\n        return result;\n    }\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/leetcode.com\/problems\/number-of-islands\/description\/ DFS of a map, O(N^2) class Solution { public: bool visit(vector&lt;vector&lt;char&gt;&gt;&amp; grid, int row, int col) { \/\/ if has any island, return true \/\/ DFS on grid const int rows = grid.size(); if (rows == 0 || row &gt;= rows || row &lt; 0) return false; const int cols = grid[0].size(); if (cols [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[66],"class_list":["post-2545","post","type-post","status-publish","format-standard","hentry","category-study","tag-leetcode-oj"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2545","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2545"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2545\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2545"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2545"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2545"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}