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 <= m, n <= 30
- grid[i][j] 是 0 或 1.
提示：
- 如果网格已经断开，则返回0。
- 如果将单个陆地更改为水域并断开岛屿连接，则返回 1。
- 否则返回2.
- 我们最多可以在2天内断开电网。
解决方案：
我们需要考虑以下步骤：
解决问题的步骤：
检查初始连通性：首先，通过确定网格中是否有多个岛屿来检查网格是否已经断开。如果已经断开连接，则返回0.
检查单个移除是否会断开岛屿的连接：迭代网格的每个单元格。暂时将单元格从 1 转换为 0（如果是 1），并通过计算岛屿数量来检查网格是否断开。如果转换单个单元格会断开岛屿的连接，则返回 1.
两天断网：如果没有单个单元转换断开岛屿，则可以通过转换任意两个相邻的陆地单元来断开电网。因此，返回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
