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中文网其它相关文章！