Shortest Bridge
easy
In a given 2D binary array grid, there are two islands. Now, we may change 0s to 1s so as to connect the two islands together to form 1 island. Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)
Constraints
1<= n <= 1000
Format
Input
First line contains an integer n. Each of next n lines contain n numbers containing either 0 or 1.
Output
Return the smallest number of 0s that must be flipped.
Example
Sample Input
3
0 1 0
0 0 0
1 1 1
Sample Output
1