1328 - 最短的桥

通过次数

10

提交次数

46

时间限制 : 1 秒
内存限制 : 512 MB

岛是由四面相连的 1 形成的一个最大组,即不会与非组内的任何其他 1 相连。grid 中恰好存在两座岛。输入一个整数n(2≤ n ≤ 100),再输入一个大小为 n x n 的矩阵 grid ,其中 1 表示陆地,0表示水域。你可以将任意数量的 0 变为 1 ,以使两座岛连接起来,变成一座岛,输出必须翻转的 0 的最小数目。

输入

n+1行,第一行输入一个正整数n;输入n x n的矩阵。

输出

必须翻转的 0 的最小数目。

样例

输入

2
0 1
1 0 

输出

1

输入

3
0 1 0
0 0 0
0 0 1

输出

2

输入

5
1 1 1 1 1
1 0 0 0 1
1 0 1 0 1
1 0 0 0 1
1 1 1 1 1

输出

1