hardGraphsPure DSA~45 min
Minimum Cells to Remove to Disconnect a Cluster
A cluster of active cells (value 1) forms a single connected island on a grid. Removing a cell deactivates it. Find the minimum number of cell removals to break the island into two or more pieces (or eliminate it entirely).
Problem
Given an m x n binary grid where 1 is land and 0 is water, the grid is 'connected' if it has exactly one island. In one day you may change a single 1 to 0. Return the minimum number of days to make the grid disconnected (zero or more than one island).
Input
An m x n binary grid.
Output
An integer: the minimum number of removals (0, 1, or 2).
Constraints
- 1 <= m, n <= 30
- grid[i][j] is 0 or 1.
- The answer never exceeds 2.
Examples
Example 1
Input
grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
Output
2
No single removal disconnects this 2x2 block, so 2 days are needed.
Example 2
Input
grid = [[1,1]]
Output
2
Both cells must go to leave fewer than one island.