Minimum Number of Days to Disconnect Island
You are given an m x n binary grid grid where 1 represents land and 0 represents water. An island is a maximal 4-directionally connected group of 1s, meaning cells are connected horizontally or vertically.
The grid is said to be connected if it has exactly one island; otherwise, it is said to be disconnected.
In one day, you are allowed to change any single land cell (1) into a water cell (0).
Return the minimum number of days to disconnect the grid.
Example 1
0 1 1 0 0 1 1 0 0 0 0 0
Input
grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]Output
2We need at least 2 days to get a disconnected grid by changing land cells such as
grid[1][1] and grid[0][2] to water.Example 2
1 1
Input
grid = [[1,1]]Output
2Changing both land cells to water gives a grid with 0 islands, which is disconnected.
Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 30
- grid[i][j] is either 0 or 1.