7273 - 填海造岛(land)

通过次数

1

提交次数

6

时间限制 : 1 秒
内存限制 : 512 MB
自2013年起,为守护国家主权和海洋权益,中国在南海开展了大规模的岛礁填海工程。经过多年建设,已在南海成功填建了美济岛、永暑岛、渚碧岛等8个重要岛屿。十年前,这些岛礁在涨潮时几乎被海水淹没,驻守官兵只能居住在狭小的高脚屋中;如今,这些地方已发展成为功能完善的现代化海上新城,配备了机场、医院、农场和学校等设施。
现在正在规划填海建造一个新的人工岛,给定一个n×n的二进制矩阵来表示海域,其中1表示陆地,0表示海水。最多只能将一处海水(0)变为陆地(1),请计算填海后能够形成的最大陆地面积。
注意:陆地的面积指的是相连的 1 所组成的区域大小。相连规则采用四连通(即上下左右四个方向相邻的 1 视为相连)。

输入

从文件land.in中读入数据。
第一行一个正整数n,表示区域的大小。
接下来的n行,一行n个数表述陆地和海水。

输出

输出到文件land.out中。
一行一个正整数,表示n×n的区域内陆地的最大面积。

样例

输入

2
1 0
0 1

输出

3

输入

3
1 0 1
0 0 0
1 0 1

输出

3

输入

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

输出

8

提示

【样例1解释】
如图所示:将左下角的海水(0)变为陆地(1),陆地的最大面积为3。

样例2解释】
如图所示:将第一列中间的海水(0)变为陆地(1),陆地的最大面积为3。

【样例3解释】
如图所示:将第二行第4个海水(0)变为陆地(1),陆地的最大面积为8。

来源

云南精英赛