原文链接: https://leetcode-cn.com/problems/minimum-number-of-days-to-disconnect-island

英文原文

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 is said disconnected.

In one day, we are allowed to change any single land cell (1) into a water cell (0).

Return the minimum number of days to disconnect the grid.

 

Example 1:

Input: grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
Output: 2
Explanation: We need at least 2 days to get a disconnected grid.
Change land grid[1][1] and grid[0][2] to water and get 2 disconnected island.

Example 2:

Input: grid = [[1,1]]
Output: 2
Explanation: Grid of full water is also disconnected ([[1,1]] -> [[0,0]]), 0 islands.

Example 3:

Input: grid = [[1,0,1,0]]
Output: 0

Example 4:

Input: grid = [[1,1,0,1,1],
               [1,1,1,1,1],
               [1,1,0,1,1],
               [1,1,0,1,1]]
Output: 1

Example 5:

Input: grid = [[1,1,0,1,1],
               [1,1,1,1,1],
               [1,1,0,1,1],
               [1,1,1,1,1]]
Output: 2

 

Constraints:

• 1 <= grid.length, grid[i].length <= 30
• grid[i][j] is 0 or 1.

中文题目

给你一个由若干 0 和 1 组成的二维网格 grid ，其中 0 表示水，而 1 表示陆地。岛屿由水平方向或竖直方向上相邻的 1 （陆地）连接形成。

如果 恰好只有一座岛屿 ，则认为陆地是 连通的 ；否则，陆地就是 分离的 。

一天内，可以将任何单个陆地单元（1）更改为水单元（0）。

返回使陆地分离的最少天数。

 

示例 1：

输入：grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
输出：2
解释：至少需要 2 天才能得到分离的陆地。
将陆地 grid[1][1] 和 grid[0][2] 更改为水，得到两个分离的岛屿。

示例 2：

输入：grid = [[1,1]]
输出：2
解释：如果网格中都是水，也认为是分离的 ([[1,1]] -> [[0,0]])，0 岛屿。

示例 3：

输入：grid = [[1,0,1,0]]
输出：0

示例 4：

输入：grid = [[1,1,0,1,1],
             [1,1,1,1,1],
             [1,1,0,1,1],
             [1,1,0,1,1]]
输出：1

示例 5：

输入：grid = [[1,1,0,1,1],
             [1,1,1,1,1],
             [1,1,0,1,1],
             [1,1,1,1,1]]
输出：2

 

提示：

• 1 <= grid.length, grid[i].length <= 30
• grid[i][j] 为 0 或 1

通过代码

高赞题解

5501. 使陆地分离的最少天数

知识点：BFS，思维题

有个比较搞喜的地方：最多删除两次必可使陆地分离。

每个格子最多会有四条边和其他格子相连。在边上的格子最多有三条边。在角上的最多有两条边。无论岛屿长成什么样子，肯定是会有角的，所以最多只需删除两次。

首先，判断输入本身就是分离的。
其次，暴力枚举删除输入中的一个 1，然后判断是否分离。
再其次，直接返回 2 就 ok 啦~

class Solution {
 public:
  bool check(const vector<vector<int>>& grid) {
    int x = 0, y = 0;
    int cnt = 0;
    for(int i = 0; i < grid.size(); i++) {
      for(int j = 0; j < grid[i].size(); j++) {
        if(grid[i][j] == 0) continue;
        cnt++;
        x = i;
        y = j;
      }
    }
    if(cnt == 0) {
      return true;
    }
    queue<pair<int, int>> q;
    bool mark[30][30] = {0};
    q.push(make_pair(x, y));
    mark[x][y] = true;
    cnt--;
    while(q.empty() == false) {
      auto f = q.front();
      q.pop();
      int dx[] = {-1,  1, 0, 0};
      int dy[] = { 0, 0, -1, 1};
      for(int i = 0; i < 4; i++) {
        int nx = dx[i] + f.first;
        int ny = dy[i] + f.second;
        if(0 <= nx && nx < grid.size() && 0 <= ny && ny < grid[0].size() && grid[nx][ny] == 1) {
          auto p = make_pair(nx, ny);
          if(mark[nx][ny]) { continue; }
          mark[nx][ny] = true;
          q.push(p);
          cnt--;
        }
      }
    }
    return cnt != 0;
  }
  int minDays(vector<vector<int>>& grid) {
    if(check(grid)) {
      return 0;
    }
    for(int i = 0; i < grid.size(); i++) {
      for(int j = 0; j < grid[0].size(); j++) {
        if(grid[i][j] == 0) {
          continue;
        }
        grid[i][j] = 0;
        if(check(grid)) {
          return 1;
        }
        grid[i][j] = 1;
      }
    }
    return 2;
  }
};

如果感觉有点意思，那就关注一下【我的公众号】吧~

统计信息

通过次数	提交次数	AC比率
2692	5868	45.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言