LeetCode 题解工作台
使陆地分离的最少天数
给你一个大小为 m x n ，由若干 0 和 1 组成的二维网格 grid ，其中 1 表示陆地， 0 表示水。 岛屿 由水平方向或竖直方向上相邻的 1 （陆地）连接形成。 如果 恰好只有一座岛屿 ，则认为陆地是 连通的 ；否则，陆地就是 分离的 。 一天内，可以将 任何单个 陆地单元（ 1 ）更改…
5
题型
6
代码语言
3
相关题
当前训练重点
困难 · 图·搜索
答案摘要
观察发现，我们总是可以通过把角落相邻的两个陆地变成水，使得岛屿分离。因此，答案只可能是 0，1 或 2。 我们跑一遍 DFS，统计当前岛屿的数量，如果数量不等于 ，也就是说不满足恰好只有一座岛屿，那么答案就是 0。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
给你一个大小为 m x n ，由若干 0 和 1 组成的二维网格 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：
输入：grid = [[1,1]] 输出：2 解释：如果网格中都是水，也认为是分离的 ([[1,1]] -> [[0,0]])，0 岛屿。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 30grid[i][j]为0或1
解题思路
方法一：脑筋急转弯
观察发现，我们总是可以通过把角落相邻的两个陆地变成水，使得岛屿分离。因此，答案只可能是 0，1 或 2。
我们跑一遍 DFS，统计当前岛屿的数量，如果数量不等于 ，也就是说不满足恰好只有一座岛屿，那么答案就是 0。
否则，我们遍历每一块陆地，把它变成水，然后再跑一遍 DFS，看看岛屿的数量是否不等于 1，如果不等于 1，说明这块陆地变成水后，岛屿分离了，答案就是 1。
遍历结束，说明必须要把两块陆地变成水，才能使得岛屿分离，因此答案就是 2。
时间复杂度 ，其中 和 分别是 grid 的行数和列数。
class Solution:
def minDays(self, grid: List[List[int]]) -> int:
if self.count(grid) != 1:
return 0
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
grid[i][j] = 0
if self.count(grid) != 1:
return 1
grid[i][j] = 1
return 2
def count(self, grid):
def dfs(i, j):
grid[i][j] = 2
for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
dfs(x, y)
m, n = len(grid), len(grid[0])
cnt = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
dfs(i, j)
cnt += 1
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
grid[i][j] = 1
return cnt
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(m \cdot n) |
| 空间 | O(m \cdot n) |
面试官常问的追问
外企场景- question_mark
Check if the candidate is able to identify the condition when the grid is already disconnected.
- question_mark
Look for the candidate's ability to explain depth-first search and its relevance to finding connected components in a grid.
- question_mark
Assess if the candidate considers the grid size and optimizes the approach accordingly.
常见陷阱
外企场景- error
Overlooking the case when the grid is already disconnected and returning unnecessary steps.
- error
Not properly handling edge cases such as small grid sizes or grids that are already water.
- error
Failing to optimize the DFS or grid traversal to minimize the number of operations required.
进阶变体
外企场景- arrow_right_alt
Allowing modifications to diagonal connections in the grid instead of only vertical and horizontal connections.
- arrow_right_alt
Implementing the solution using a breadth-first search (BFS) instead of DFS.
- arrow_right_alt
Handling multiple islands and calculating the number of days to disconnect all of them.