---

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

• 标签：深度优先搜索、广度优先搜索、数组、矩阵、强连通分量
• 难度：困难

题目链接

• 1568. 使陆地分离的最少天数 - 力扣

题目大意

描述：给定一个 $m \times n$ 的二维网格 $grid$，其中 $1$ 表示陆地，$0$ 表示水。每天可以将任意一个陆地格子变成水。

初始时网格恰好包含一个连通分量（即所有陆地连通）。

要求：返回最少需要多少天，使得网格变成至少两个连通分量。

说明：

• $1 \le m, n \le 30$。
• $grid[i][j]$ 为 $0$ 或 $1$。

示例：

• 示例 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 岛屿。

解题思路

思路 1：分类讨论

1. 核心思想

关键观察：答案最多为 $2$。因为对于任何非 $1 \times 1$ 或 $2 \times 2$ 的连通陆地，总存在一个角落点，移除它就可以断开连接。更准确地说：

• 如果陆地格子总数 $\le 1$ 或初始已不连通，返回 $0$。
• 如果存在一个格子（桥接点），移除它就能使陆地不连通，返回 $1$。
• 否则，移除一个角落的格子（如 $2 \times 2$ 块），返回 $2$。

实际上，答案是 $0$、$1$ 或 $2$ 之一。

2. 具体步骤

第 1 步：计算陆地块数 $land\_cnt$。如果为 $0$ 或初始不连通（陆地块数 $> 1$），返回 $0$。

第 2 步：尝试移除每个陆地格子，检查移除后剩余陆地是否连通。

• 遍历所有格子，如果是陆地，暂时改成水。
• 统计剩余陆地的连通分量数。
• 如果分量数 $> 1$ 或没有陆地，返回 $1$。
• 恢复该格子。

第 3 步：如果没有任何一个格子移除后导致陆地分离，返回 $2$。

3. 为什么答案是 0/1/2？

• 如果陆地块数 $= 0$，已经是 $0$ 个连通分量（$< 1$），答案为 $0$。
• 如果初始有 $> 1$ 个连通分量，答案为 $0$。
• 如果存在"割点"（articulation point），移除它即可断开，答案为 $1$。
• 因为网格图是平面图，移除一个 $2 \times 2$ 块的角落总是破坏连通性，所以上限是 $2$。

4. 举例说明

以 $grid = [[1,0,1,0]]$ 为例：

初始有两个连通分量，返回 $0$。

以 $grid = [[1,1,0,1,1]]$ 为例：

中间是水，两头各一个连通分量，返回 $0$。

以 $grid = [[1,1],[1,1]]$ 为例：

$4$ 个格子构成连通块，不存在单个割点。移除任一个后剩下 $3$ 个仍连通。因此返回 $2$。

以 $grid = [[1,1,1],[1,0,0],[1,0,0]]$ 为例：

存在割点（如右上角），移除后断开，返回 $1$。

思路 1：代码

class Solution:
    def minDays(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def count_islands():
            """统计陆地的连通分量数"""
            visited = [[False] * n for _ in range(m)]
            cnt = 0
            for i in range(m):
                for j in range(n):
                    if grid[i][j] == 1 and not visited[i][j]:
                        cnt += 1
                        if cnt > 1:
                            return cnt
                        # DFS
                        stack = [(i, j)]
                        visited[i][j] = True
                        while stack:
                            x, y = stack.pop()
                            for dx, dy in dirs:
                                nx, ny = x + dx, y + dy
                                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1 and not visited[nx][ny]:
                                    visited[nx][ny] = True
                                    stack.append((nx, ny))
            return cnt

        # 检查初始状态
        if count_islands() != 1:
            return 0

        # 尝试移除每个陆地格子
        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

思路 1：复杂度分析

• 时间复杂度：$O((m \times n)^2)$。每次移除后 DFS。但在本题约束下（$m,n \le 30$），最多 $900$ 个格子，每次 DFS $O(900)$，总 $O(8.1 \times 10^5)$，可行。
• 空间复杂度：$O(m \times n)$。