断开岛屿连接的最少天数

1568。断开岛屿连接的最短天数

难度：难

主题：数组、深度优先搜索、广度优先搜索、矩阵、强连通分量

给你一个 m x n 二进制网格，其中 1 代表土地，0 代表水。 岛屿 是最大4 向（水平或垂直）连接的1 组。

如果我们恰好有一个岛屿，则称网格已连接，否则称已断开。

有一天，我们可以将任何一个陆地单元（1）变成水单元（0）。

返回断开电网的最小天数。

示例1：

• 输入： grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
• 输出： 2
• 说明：我们至少需要 2 天才能断开电网。 将陆地网格[1][1]和网格[0][2]更改为水网格并获得2个不相连的岛屿。

示例2：

• 输入： grid = [[1,1]]
• 输出： 2
• 解释：满水网格也断开（[[1,1]] -> [[0,0]]），0个岛屿。

约束：

• m == grid.length
• n == grid[i].length
• 1
• grid[i][j] 为 0 或 1。

提示：

1. 如果网格已经断开，则返回 0。
2. 如果将单个陆地更改为水域，则返回 1 断开岛屿连接。
3. 否则返回 2。
4. 我们最多可以在2天内断开电网。

解决方案：

我们需要考虑以下步骤：

解决问题的步骤：

1. 检查初始连通性：首先，通过确定网格中是否存在多个岛屿来检查网格是否已经断开。如果已经断开连接，则返回 0。

2. 检查单个移除是否会断开岛屿的连接：迭代网格的每个单元格。暂时将单元格从 1 转换为 0（如果是 1），并通过计算岛屿数量来检查网格是否断开。如果转换单个单元格会断开岛的连接，则返回 1。

3. 两天断网：如果没有单个单元转换断开岛屿，则可以通过转换任意两个相邻的陆地单元来断开电网。因此，返回 2。

主要功能：

• DFS（深度优先搜索） 查找并计算岛屿。
• isConnected 检查网格是否已连接。

让我们用 PHP 实现这个解决方案：1568。断开岛屿连接的最短天数

<?php
// Example usage:
$grid1 = [
    [0, 1, 1, 0],
    [0, 1, 1, 0],
    [0, 0, 0, 0]
];
echo minDays($grid1); // Output: 2

$grid2 = [
    [1, 1]
];
echo minDays($grid2); // Output: 2
?>

解释：

• minDays() 函数处理主要逻辑。
• countIslands() 使用 DFS 计算存在的岛屿数量。
• dfs() 是探索网格并标记访问过的陆地单元的递归函数。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是断开岛屿连接的最少天数的详细内容。更多信息请关注PHP中文网其他相关文章！