1096. Shortest Bridge

Given a grid containing exactly two islands (4-directionally connected groups of 1s) in a sea of 0s, return the minimum number of 0s that must be flipped to 1 to connect the two islands. The input is JSON {grid}.

Input: JSON {grid}.

Output: Integer — the minimum flips to bridge the islands.

Examples

Input: {"grid":[[0,1,0],[0,0,0],[0,0,1]]}
Output: 2
Explanation: Two cells bridge the islands.

Input: {"grid":[[1,0],[0,1]]}
Output: 1
Explanation: One cell connects them.

Input: {"grid":[[1,1,0,0],[0,0,0,1]]}
Output: 2
Explanation: Two flips needed.

Constraints

• 2<=rows,cols<=100
• exactly two islands

Asked by