Hard

题目描述

给你一个大小为 m x n 的二进制网格 grid，其中 1 表示陆地，0 表示水。岛屿是由四面（水平或竖直）相连的 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 个分离的岛屿。

示例 2：

输入：grid = [[1,1]]
输出：2
解释：如果网格中都是水，那么也是分离的（[[1,1]] -> [[0,0]]），0 个岛屿。

约束条件：

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

提示：

  • 如果网格已经分离，则返回 0
  • 如果改变一个陆地为水就能分离岛屿，则返回 1
  • 否则返回 2
  • 我们最多可以在 2 天内分离网格

解题思路

这道题的核心思想是分析岛屿的连通性，答案只可能是 0、1 或 2。

思路分析：

  1. 情况0（返回0）：网格已经分离，即岛屿数量不等于1

  2. 情况1（返回1）：移除一个陆地单元格就能使岛屿分离。这种情况包括：

    • 整个岛屿只有一个陆地单元格
    • 存在"关键点"（articulation point/cut vertex），移除后岛屿分离

  3. 情况2（返回2）：其他所有情况都最多需要2天

算法步骤：

  1. 首先检查当前岛屿数量，如果不是1个则返回0
  2. 如果岛屿只有1个陆地单元格，返回1
  3. 尝试移除每个陆地单元格，检查是否能使岛屿分离，如果可以则返回1
  4. 否则返回2

关键在于实现一个高效的连通分量计算函数，使用DFS或BFS都可以。

代码实现

class Solution {
public:
    int minDays(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        
        // 计算岛屿数量
        auto countIslands = [&]() {
            vector<vector<bool>> visited(m, vector<bool>(n, false));
            int count = 0;
            
            function<void(int, int)> dfs = [&](int i, int j) {
                if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || grid[i][j] == 0) {
                    return;
                }
                visited[i][j] = true;
                dfs(i + 1, j);
                dfs(i - 1, j);
                dfs(i, j + 1);
                dfs(i, j - 1);
            };
            
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 1 && !visited[i][j]) {
                        dfs(i, j);
                        count++;
                    }
                }
            }
            return count;
        };
        
        // 统计陆地数量
        int landCount = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) landCount++;
            }
        }
        
        // 检查初始状态
        int islands = countIslands();
        if (islands != 1) return 0;
        if (landCount == 1) return 1;
        
        // 尝试移除每个陆地
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    grid[i][j] = 0;
                    if (countIslands() != 1) {
                        return 1;
                    }
                    grid[i][j] = 1;
                }
            }
        }
        
        return 2;
    }
};

class Solution:
    def minDays(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        def count_islands():
            visited = [[False] * n for _ in range(m)]
            count = 0
            
            def dfs(i, j):
                if i < 0 or i >= m or j < 0 or j >= n or visited[i][j] or grid[i][j] == 0:
                    return
                visited[i][j] = True
                dfs(i + 1, j)
                dfs(i - 1, j)
                dfs(i, j + 1)
                dfs(i, j - 1)
            
            for i in range(m):
                for j in range(n):
                    if grid[i][j] == 1 and not visited[i][j]:
                        dfs(i, j)
                        count += 1
            return count
        
        # 统计陆地数量
        land_count = sum(grid[i][j] for i in range(m) for j in range(n))
        
        # 检查初始状态
        islands = count_islands()
        if islands != 1:
            return 0
        if land_count == 1:
            return 1
        
        # 尝试移除每个陆地
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    grid[i][j] = 0
                    if count_islands() != 1:
                        return 1
                    grid[i][j] = 1
        
        return 2

public class Solution {
    public int MinDays(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        
        int CountIslands() {
            bool[,] visited = new bool[m, n];
            int count = 0;
            
            void Dfs(int i, int j) {
                if (i < 0 || i >= m || j < 0 || j >= n || visited[i, j] || grid[i][j] == 0) {
                    return;
                }
                visited[i, j] = true;
                Dfs(i + 1, j);
                Dfs(i - 1, j);
                Dfs(i, j + 1);
                Dfs(i, j - 1);
            }
            
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 1 && !visited[i, j]) {
                        Dfs(i, j);
                        count++;
                    }
                }
            }
            return count;
        }
        
        // 统计陆地数量
        int landCount = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) landCount++;
            }
        }
        
        // 检查初始状态
        int islands = CountIslands();
        if (islands != 1) return 0;
        if (landCount == 1) return 1;
        
        // 尝试移除每个陆地
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    grid[i][j] = 0;
                    if (CountIslands() != 1) {
                        return 1;
                    }
                    grid[i][j] = 1;
                }
            }
        }
        
        return 2;
    }
}

var minDays = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    
    function countIslands(grid) {
        const visited = Array(m).fill().map(() => Array(n).fill(false));
        let count = 0;
        
        function dfs(i, j) {
            if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || grid[i][j] === 0) {
                return;
            }
            visited[i][j] = true;
            for (const [di, dj] of directions) {
                dfs(i + di, j + dj);
            }
        }
        
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                if (grid[i][j] === 1 && !visited[i][j]) {
                    count++;
                    dfs(i, j);
                }
            }
        }
        return count;
    }
    
    // Check if already disconnected
    if (countIslands(grid) !== 1) {
        return 0;
    }
    
    // Try removing each land cell
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 1) {
                grid[i][j] = 0;
                if (countIslands(grid) !== 1) {
                    return 1;
                }
                grid[i][j] = 1;
            }
        }
    }
    
    return 2;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m²n²)，其中 m 和 n 是网格的维度。最坏情况下需要尝试移除每个陆地单元格（O(mn)），每次都要进行一次DFS遍历（O(mn)）
空间复杂度O(mn)，主要用于DFS的递归栈空间和visited数组

相关题目