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.lengthn == grid[i].length1 grid[i][j] 是 0 或 1.
提示：
如果网格已经断开，则返回0。如果将单个陆地更改为水域并断开岛屿连接，则返回 1。否则返回2.我们最多可以在2天内断开电网。
解决方案：
我们需要考虑以下步骤：
解决问题的步骤：
检查初始连通性：首先，通过确定网格中是否有多个岛屿来检查网格是否已经断开。如果已经断开连接，则返回0.
检查单个移除是否会断开岛屿的连接：迭代网格的每个单元格。暂时将单元格从 1 转换为 0（如果是 1），并通过计算岛屿数量来检查网格是否断开。如果转换单个单元格会断开岛屿的连接，则返回 1.
两天断网：如果没有单个单元转换断开岛屿，则可以通过转换任意两个相邻的陆地单元来断开电网。因此，返回2.
主要功能：
dfs（深度优先搜索） 查找和计算岛屿。isconnected 检查网格是否已连接。
让我们用 php 实现这个解决方案：1568。断开岛屿连接的最短天数
解释：
mindays() 函数处理主要逻辑。countislands() 使用 dfs 计算存在的岛屿数量。dfs() 是探索网格并标记访问过的陆地单元的递归函数。
联系链接
如果您发现本系列有帮助，请考虑在 github 上给存储库 一颗星，或在您最喜欢的社交网络上分享该帖子?。您的支持对我来说意义重大！
如果您想要更多类似的有用内容，请随时关注我：
领英github
以上就是断开岛屿连接的最少天数的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1244577.html
微信扫一扫 
支付宝扫一扫 
