← 返回 tesla 的题目列表Shortest Bridge
类型：online_judge
Problem: Shortest Bridge
Given an n x n binary matrix grid:
1 represents land;
0 represents water;
there are exactly two islands in the grid.
An island is a group of 1s connected 4-directionally, meaning horizontally or vertically.
You may flip any number of 0s into 1s to connect the two islands. Return the minimum number of 0s that must be flipped.
Input Format
The first line contains an integer n.
The next n lines each contain n binary digits. The digits may be separated by spaces or written continuously.
Output Format
Print one integer: the minimum number of 0s to flip.
Constraints
2 <= n <= 100
grid[i][j] is 0 or 1
There are exactly two islands in grid
Example
Input:
2
0 1
1 0
Output:
1
Example
Input
2
0 1
1 0
Output
1