{"id":373,"date":"2017-09-20T19:23:43","date_gmt":"2017-09-21T02:23:43","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=373"},"modified":"2018-11-16T12:50:56","modified_gmt":"2018-11-16T20:50:56","slug":"leetcode-200-number-of-islands","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-200-number-of-islands\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 200. Number of Islands"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 200. Number of Islands  - \u5237\u9898\u627e\u5de5\u4f5c EP65\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/XSmgFKe-XYU?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>Given a 2d grid map of\u00a0<code>'1'<\/code>s (land) and\u00a0<code>'0'<\/code>s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.<\/p>\n<p><i><b>Example 1:<\/b><\/i><\/p>\n<pre>11110\r\n11010\r\n11000\r\n00000<\/pre>\n<p>Answer: 1<\/p>\n<p><i><b>Example 2:<\/b><\/i><\/p>\n<pre>11000\r\n11000\r\n00100\r\n00011<\/pre>\n<h1><strong>Idea:\u00a0DFS<\/strong><\/h1>\n<p>Use DFS to find a connected component (an island) and mark all the nodes to 0.<\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/200-ep65-1.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-377\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/200-ep65-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/200-ep65-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/200-ep65-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/200-ep65-1-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/200-ep65-1-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p>Time complexity:\u00a0O(mn)<\/p>\n<p>Space complexity: O(mn)<\/p>\n<h1><strong>Solution<\/strong><\/h1>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Time complexity: O(mn)\r\n\/\/ Running time: 6 ms\r\nclass Solution {\r\npublic:\r\n    int numIslands(vector&lt;vector&lt;char&gt;&gt;&amp; grid) {\r\n        if (grid.empty()) return 0;\r\n        int m = grid.size();\r\n        int n = grid[0].size();\r\n        int ans = 0;\r\n        for (int y = 0; y &lt; m; ++y)\r\n            for (int x = 0; x &lt; n; ++x) {\r\n                ans += grid[y][x] - '0';\r\n                dfs(grid, x, y, m, n);\r\n            }\r\n        return ans;                \r\n    }   \r\nprivate:\r\n    void dfs(vector&lt;vector&lt;char&gt;&gt;&amp; grid, int x, int y, int m, int n) {\r\n        if (x &lt; 0 || y &lt; 0 || x &gt;= n || y &gt;= m || grid[y][x] == '0')\r\n            return;\r\n        grid[y][x] = '0';\r\n        dfs(grid, x + 1, y, m, n);\r\n        dfs(grid, x - 1, y, m, n);\r\n        dfs(grid, x, y + 1, m, n);\r\n        dfs(grid, x, y - 1, m, n);\r\n    }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Time Complexity: O(mn)\r\n\/\/ Running time: 13 ms\r\nclass Solution {\r\n    public int numIslands(char[][] grid) {\r\n        int m = grid.length;\r\n        if (m == 0) return 0;\r\n        int n = grid[0].length;\r\n        \r\n        int ans = 0;\r\n        for (int y = 0; y &lt; m; ++y)\r\n            for (int x = 0; x &lt; n; ++x)\r\n                if (grid[y][x] == '1') {\r\n                    ++ans;\r\n                    dfs(grid, x, y, n, m);\r\n                }\r\n        \r\n        return ans;\r\n    }\r\n    \r\n    private void dfs(char[][] grid, int x, int y, int n, int m) {\r\n        if (x &lt; 0 || y &lt; 0 || x &gt;= n || y &gt;= m || grid[y][x] == '0')\r\n            return;\r\n        grid[y][x] = '0';\r\n        dfs(grid, x + 1, y, n, m);\r\n        dfs(grid, x - 1, y, n, m);\r\n        dfs(grid, x, y + 1, n, m);\r\n        dfs(grid, x, y - 1, n, m);\r\n    }\r\n}<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:python decode:true \">\"\"\"\r\nAuthor: Huahua\r\nTime Complexity: O(mn)\r\nRunning Time: 102 ms\r\n\"\"\"\r\nclass Solution(object):\r\n    def numIslands(self, grid):\r\n        \"\"\"\r\n        :type grid: List[List[str]]\r\n        :rtype: int\r\n        \"\"\"\r\n        m = len(grid)\r\n        if m == 0: return 0\r\n        n = len(grid[0])\r\n        \r\n        ans = 0\r\n        for y in xrange(m):\r\n            for x in xrange(n):\r\n                if grid[y][x] == '1':\r\n                    ans += 1\r\n                    self.__dfs(grid, x, y, n, m)\r\n        return ans\r\n    \r\n    def __dfs(self, grid, x, y, n, m):\r\n        if x &lt; 0 or y &lt; 0 or x &gt;=n or y &gt;= m or grid[y][x] == '0':\r\n            return\r\n        grid[y][x] = '0'\r\n        self.__dfs(grid, x + 1, y, n, m)\r\n        self.__dfs(grid, x - 1, y, n, m)\r\n        self.__dfs(grid, x, y + 1, n, m)\r\n        self.__dfs(grid, x, y - 1, n, m)\r\n<\/pre>\n<\/div><\/div>\n<h1><strong>Related Problems<\/strong><\/h1>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-695-max-area-of-island\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 695. Max Area of Island<\/a><\/li>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-547-friend-circles\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 547. Friend Circles<\/a><\/li>\n<li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-827-making-a-large-island\/\">\u82b1\u82b1\u9171 LeetCode 827. Making A Large Island<\/a><\/li>\n<li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-934-shortest-bridge\/\">\u82b1\u82b1\u9171 LeetCode 934. Shortest Bridge<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Problem: Given a 2d grid map of\u00a0&#8216;1&#8217;s (land) and\u00a0&#8216;0&#8217;s (water), count the number of islands. An island is surrounded by water and is formed by&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[76,44],"tags":[102,33,222,433],"class_list":["post-373","post","type-post","status-publish","format-standard","hentry","category-graph","category-searching","tag-connected-components","tag-dfs","tag-easy","tag-island","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/373","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=373"}],"version-history":[{"count":9,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/373\/revisions"}],"predecessor-version":[{"id":4328,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/373\/revisions\/4328"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=373"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=373"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=373"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}