{"id":7318,"date":"2020-08-30T00:57:00","date_gmt":"2020-08-30T07:57:00","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7318"},"modified":"2020-09-14T22:23:16","modified_gmt":"2020-09-15T05:23:16","slug":"leetcode-1568-minimum-number-of-days-to-disconnect-island","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-1568-minimum-number-of-days-to-disconnect-island\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1568. Minimum Number of Days to Disconnect Island"},"content":{"rendered":"\n

Given a 2D grid<\/code> consisting of 1<\/code>s (land) and 0<\/code>s (water).  An island<\/em> is a maximal 4-directionally (horizontal or vertical) connected group of 1<\/code>s.<\/p>\n\n\n\n

The grid is said to be connected<\/strong> if we have exactly one island<\/strong>, otherwise is said disconnected<\/strong>.<\/p>\n\n\n\n

In one day, we are allowed to change any <\/strong>single land cell (1)<\/code> into a water cell (0)<\/code>.<\/p>\n\n\n\n

Return the minimum number of days<\/em> to disconnect the grid.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]\nOutput:<\/strong> 2\nExplanation:<\/strong> We need at least 2 days to get a disconnected grid.\nChange land grid[1][1] and grid[0][2] to water and get 2 disconnected island.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> grid = [[1,1]]\nOutput:<\/strong> 2\nExplanation: <\/strong>Grid of full water is also disconnected ([[1,1]] -> [[0,0]]), 0 islands.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> grid = [[1,0,1,0]]\nOutput:<\/strong> 0\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input:<\/strong> grid = [[1,1,0,1,1],\n               [1,1,1,1,1],\n               [1,1,0,1,1],\n               [1,1,0,1,1]]\nOutput:<\/strong> 1\n<\/pre>\n\n\n\n
Example 5:<\/strong><\/p>\n\n\n\n
Input:<\/strong> grid = [[1,1,0,1,1],\n               [1,1,1,1,1],\n               [1,1,0,1,1],\n               [1,1,1,1,1]]\nOutput:<\/strong> 2\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= grid.length, grid[i].length <= 30<\/code><\/li>
  • grid[i][j]<\/code> is 0<\/code> or 1<\/code>.<\/li><\/ul>\n\n\n\n
    Solution: Brute Force<\/strong><\/h2>\n\n\n\n
    We need at most two days to disconnect an island. 
    1. check if we have more than one islands. (0 days)
    2. For each 1 cell, change it to 0 and check how many islands do we have. (1 days)
    3. Otherwise, 2 days<\/p>\n\n\n\n
    Time complexity: O(m^2*n^2)
    Space complexity: O(m*n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \nclass Solution {\npublic:\n  int minDays(vector>& grid) {\n    const int n = grid.size();\n    const int m = grid[0].size();    \n    const vector dirs{0, 1, 0, -1, 0};\n    vector seen(n * m);    \n    function dfs = [&](int x, int y) {\n      if (x < 0 || y < 0 || x >= m || y >= n) return;\n      if (grid[y][x] == 0) return;\n      if (seen[y * m + x]++) return;      \n      for (int i = 0; i < 4; ++i)        \n        dfs(x + dirs[i], y + dirs[i + 1]);\n    };\n    \n    function disconnected = [&]() {\n      int count = 0;\n      fill(begin(seen), end(seen), 0);\n      for (int y = 0; y < n; ++y)\n        for (int x = 0; x < m; ++x)\n          if (grid[y][x] && !seen[y * m + x]) {\n            dfs(x, y);\n            if (++count > 1) return true;\n          }\n      return false;\n    };\n    \n    if (disconnected()) return 0;\n    \n    for (int y = 0; y < n; ++y)\n      for (int x = 0; x < m; ++x) {\n        if (!grid[y][x]) continue;\n        grid[y][x] = 0;\n        if (disconnected()) return 1;\n        grid[y][x] = 1;\n      }\n    return 2;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Given a 2D grid consisting of 1s (land) and 0s (water).  An island is a maximal 4-directionally (horizontal or vertical) connected group of 1s. The grid is said to be connected if we have exactly one island, otherwise…<\/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":[33,77,177],"class_list":["post-7318","post","type-post","status-publish","format-standard","hentry","category-graph","tag-dfs","tag-graph","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7318","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=7318"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7318\/revisions"}],"predecessor-version":[{"id":7383,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7318\/revisions\/7383"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7318"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7318"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7318"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}