{"id":2808,"date":"2018-04-30T03:59:51","date_gmt":"2018-04-30T10:59:51","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2808"},"modified":"2018-05-02T19:54:09","modified_gmt":"2018-05-03T02:54:09","slug":"leetcode-827-making-a-large-island","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-827-making-a-large-island\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 827. Making A Large Island"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 827. Making A Large Island - \u5237\u9898\u627e\u5de5\u4f5c EP187\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/KqkXZpRB1x8?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<h1><strong>Problem<\/strong><\/h1>\n<p>In a 2D grid of\u00a0<code>0<\/code>s and\u00a0<code>1<\/code>s, we change at most one\u00a0<code>0<\/code>\u00a0to a\u00a0<code>1<\/code>.<\/p>\n<p>After, what is the size of the largest island?\u00a0(An island is a 4-directionally connected group of\u00a0<code>1<\/code>s).<\/p>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong>[[1, 0], [0, 1]]\r\n<strong>Output:<\/strong> 3\r\n<strong>Explanation:<\/strong> Change one 0 to 1 and connect two 1s, then we get an island with area = 3.\r\n<\/pre>\n<p><strong>Example 2:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong>[[1, 1], [1, 0]]\r\n<strong>Output:<\/strong> 4\r\n<strong>Explanation: <\/strong>Change the 0 to 1 and make the island bigger, only one island with area = 1.<\/pre>\n<p><strong>Example 3:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong>[[1, 1], [1, 1]]\r\n<strong>Output:<\/strong> 4\r\n<strong>Explanation:<\/strong> Can't change any 0 to 1, only one island with area = 1.<\/pre>\n<p>Notes:<\/p>\n<ul>\n<li><code>1 &lt;= grid.length = grid[0].length &lt;= 50<\/code>.<\/li>\n<li><code>0 &lt;= grid[i][j] &lt;= 1<\/code>.<\/li>\n<\/ul>\n<h1><strong>Solution<\/strong><\/h1>\n<p>Step 1: give each connected component a unique id and count its ara.<\/p>\n<p>Step 2: for each 0 zero, check its 4 neighbours, sum areas up by unique ids.<\/p>\n<p>Time complexity: O(n*m)<\/p>\n<p>Space complexity: O(n*m)<\/p>\n<p>C++<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 14 ms\r\nclass Solution {\r\npublic:\r\n  int largestIsland(vector&lt;vector&lt;int&gt;&gt;&amp; grid) {\r\n    color_ = 1;\r\n    g_ = &amp;grid;\r\n    m_ = grid.size();\r\n    n_ = grid[0].size();\r\n    unordered_map&lt;int, int&gt; areas; \/\/ color -&gt; area\r\n    int ans = 0;\r\n    for (int i = 0; i &lt; m_; ++i)\r\n      for (int j = 0; j &lt; n_; ++j)\r\n        if (grid[i][j] == 1) {\r\n          ++color_;\r\n          areas[color_] = getArea(j, i);\r\n          ans = max(ans, areas[color_]);\r\n        }\r\n    for (int i = 0; i &lt; m_; ++i)\r\n      for (int j = 0; j &lt; n_; ++j)\r\n        if (grid[i][j] == 0) {                    \r\n          int area = 1;\r\n          for (int color : set&lt;int&gt;{getColor(j, i - 1), getColor(j, i + 1),\r\n                                    getColor(j - 1, i), getColor(j + 1, i)}) \r\n            area += areas[color];\r\n          ans = max(ans, area);\r\n        }\r\n    return ans;\r\n  }\r\nprivate:\r\n  int m_;\r\n  int n_;\r\n  int color_;\r\n  vector&lt;vector&lt;int&gt;&gt;* g_; \/\/ does not own the object.\r\n  \r\n  int getColor(int x, int y) {\r\n    return (x &lt; 0 || x &gt;= n_ || y &lt; 0 || y &gt;= m_) ? 0 : (*g_)[y][x];\r\n  }\r\n  \r\n  \/\/ Return the area of a connected component, set all elements to color_.\r\n  int getArea(int x, int y) {\r\n    if (x &lt; 0 || x &gt;= n_ || y &lt; 0 || y &gt;= m_ || (*g_)[y][x] != 1) return 0;\r\n    (*g_)[y][x] = color_;\r\n    return 1 + getArea(x - 1, y) + getArea(x + 1, y) \r\n             + getArea(x, y - 1) + getArea(x, y + 1);\r\n  }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem In a 2D grid of\u00a00s and\u00a01s, we change at most one\u00a00\u00a0to a\u00a01. After, what is the size of the largest island?\u00a0(An island is a&#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],"tags":[102,33,77,217],"class_list":["post-2808","post","type-post","status-publish","format-standard","hentry","category-graph","tag-connected-components","tag-dfs","tag-graph","tag-hard","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2808","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=2808"}],"version-history":[{"count":9,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2808\/revisions"}],"predecessor-version":[{"id":2825,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2808\/revisions\/2825"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2808"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2808"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2808"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}