1568. Minimum Number of Days to Disconnect Island¶
题目信息¶
- 题号:
1568
- 难度:
Hard
- 主题:
网格、连通分量、割点
- 原题:
- 重点:
每天可把一个陆地格变为水;当陆地连通分量数量不等于一时视为断开,答案只可能为
0、1或2
题目重述¶
给定二进制网格 grid,1 表示陆地,0 表示水。上下左右相邻的陆地格属于同一座岛屿。
每天可以选择一个陆地格并把它变为水。若网格中岛屿数量为 0 或大于 1,则网格已断开。请返回使网格断开所需的最少天数。
1 <= grid.length, grid[i].length <= 30。
自建示例¶
完整二乘二陆地需要删除两个格子才能断开:
输入:grid = [[1,1],[1,1]]
输出:2
解释:删除任意一个格子后其余三个仍连通;删除一对对角位置后会形成两个岛屿。
单个陆地格删除后没有岛屿:
输入:grid = [[1]]
输出:1
解释:一天后陆地连通分量数量变为零。