Problem Statement

You are given a square grid (n x n) made up of 1s (land) and 0s (water). There are exactly two separate islands in the grid.

An island is defined as a group of connected 1s that are not connected to any other 1s.

Return the minimum number of 0s that need to be flipped to connect the two islands into one if you can change any 0 to 1 to connect the two islands.

Examples

Example 1:

• Input: grid =

[[1, 1, 0, 0, 0],
 [1, 0, 0, 0, 0],
 [0, 0, 1, 1, 0],
 [0, 0, 0, 1, 1],
 [0, 0, 0, 0, 0]]

• Expected Output: 2