描述
自2013年起,为守护国家主权和海洋权益,中国在南海开展了大规模的岛礁填海工程。经过多年建设,已在南海成功填建了美济岛、永暑岛、渚碧岛等8个重要岛屿。十年前,这些岛礁在涨潮时几乎被海水淹没,驻守官兵只能居住在狭小的高脚屋中;如今,这些地方已发展成为功能完善的现代化海上新城,配备了机场、医院、农场和学校等设施。
现在正在规划填海建造一个新的人工岛,给定一个$ n \times n$的二进制矩阵来表示海域,其中1表示陆地,0表示海水。最多只能将一处海水(0)变为陆地(1),请计算填海后能够形成的最大陆地面积。
注意:陆地的面积指的是相连的 1 所组成的区域大小。相连规则采用四连通(即上下左右四个方向相邻的 1 视为相连)。
输入
从文件land.in中读入数据。<br>
第一行一个正整数$n$,表示区域的大小。<br>
接下来的$n$行,一行$n$个数表述陆地和海水。<br>
输出
输出到文件land.out中。<br>
一行一个正整数,表示$ n \times n$的区域内陆地的最大面积。<br>
样例
- 复制
- 复制
- 复制
- 复制
- 复制
- 复制
提示
【样例1解释】<br>
如图所示:将左下角的海水(0)变为陆地(1),陆地的最大面积为3。<br>
<br>
样例2解释】<br>
如图所示:将第一列中间的海水(0)变为陆地(1),陆地的最大面积为3。<br>
<br>
【样例3解释】<br>
如图所示:将第二行第4个海水(0)变为陆地(1),陆地的最大面积为8。<br>
<br>
$ 1 \le n \le 1000$

关注我们