1328 - 最短的桥
时间限制 : 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