1101. Minimum Days to Disconnect Island

Given a binary grid where 1 is land and 0 is water, the grid is 'connected' if it has exactly one island (4-directionally connected land). Each day you may turn one land cell into water. Return the minimum number of days to make the grid disconnected (zero islands or more than one). The answer is always 0, 1, or 2. The input is JSON {grid}.

Input: JSON {grid}.

Output: Integer — the minimum days (0, 1, or 2).

Examples

Input: {"grid":[[0,1,1,0],[0,1,1,0],[0,0,0,0]]}
Output: 2
Explanation: A 2x2 block needs two removals.

Input: {"grid":[[1,1]]}
Output: 2
Explanation: A solid strip needs two.

Input: {"grid":[[1,0,1,0]]}
Output: 0
Explanation: Already disconnected.

Constraints

• 1<=rows,cols<=30

Asked by