Given a 2D grid consisting of 1s (land) and 0s (water).  An island is a maximal 4-directionally (horizontal or vertical) connected group of 1s.

The grid is said to be connected if we have exactly one island, otherwise is said disconnected.

In one day, we 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:

Input: grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
Output: 2
Explanation: We need at least 2 days to get a disconnected grid.
Change land grid[1][1] and grid[0][2] to water and get 2 disconnected island.


Example 2:

Input: grid = [[1,1]]
Output: 2
Explanation: Grid of full water is also disconnected ([[1,1]] -> [[0,0]]), 0 islands.


Example 3:

Input: grid = [[1,0,1,0]]
Output: 0


Example 4:

Input: grid = [[1,1,0,1,1],
[1,1,1,1,1],
[1,1,0,1,1],
[1,1,0,1,1]]
Output: 1


Example 5:

Input: grid = [[1,1,0,1,1],
[1,1,1,1,1],
[1,1,0,1,1],
[1,1,1,1,1]]
Output: 2


Constraints:

• 1 <= grid.length, grid[i].length <= 30
• grid[i][j] is 0 or 1.

## Solution: Brute Force

We need at most two days to disconnect an island.
1. check if we have more than one islands. (0 days)
2. For each 1 cell, change it to 0 and check how many islands do we have. (1 days)
3. Otherwise, 2 days

Time complexity: O(m^2*n^2)
Space complexity: O(m*n)

## C++

If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website

Paypal
Venmo
huahualeetcode