1568. Minimum Number of Days to Disconnect Island

题目信息

题号:

1568

难度:

Hard

主题:

网格、连通分量、割点

原题:

LeetCode 1568

重点:

每天可把一个陆地格变为水;当陆地连通分量数量不等于一时视为断开,答案只可能为 0、1 或 2

题目重述

给定二进制网格 grid,1 表示陆地,0 表示水。上下左右相邻的陆地格属于同一座岛屿。

每天可以选择一个陆地格并把它变为水。若网格中岛屿数量为 0 或大于 1,则网格已断开。请返回使网格断开所需的最少天数。

1 <= grid.length, grid[i].length <= 30。

自建示例

完整二乘二陆地需要删除两个格子才能断开:

输入:grid = [[1,1],[1,1]]
输出:2
解释:删除任意一个格子后其余三个仍连通;删除一对对角位置后会形成两个岛屿。

单个陆地格删除后没有岛屿:

输入:grid = [[1]]
输出:1
解释:一天后陆地连通分量数量变为零。