You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

自2013年起，为守护国家主权和海洋权益，中国在南海开展了大规模的岛礁填海工程。经过多年建设，已在南海成功填建了美济岛、永暑岛、渚碧岛等8个重要岛屿。十年前，这些岛礁在涨潮时几乎被海水淹没，驻守官兵只能居住在狭小的高脚屋中；如今，这些地方已发展成为功能完善的现代化海上新城，配备了机场、医院、农场和学校等设施。

现在正在规划填海建造一个新的人工岛，给定一个 n×n的二进制矩阵来表示海域，其中1表示陆地，0表示海水。最多只能将一处海水（0）变为陆地（1），请计算填海后能够形成的最大陆地面积。

注意：陆地的面积指的是相连的 1 所组成的区域大小。相连规则采用四连通（即上下左右四个方向相邻的 1 视为相连）。

输入格式

从文件 land.in 读入。

• 第一行：一个正整数 $n$，表示矩阵边长。
• 接下来 $n$ 行：每行 $n$ 个数字（$0$ 或 $1$），表示海域状态。

输出格式

输出到文件 land.out。 一行一个正整数，表示填海后能得到的最大陆地面积。

样例输入输出

样例

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$。

  

数据范围

对于所有测试数据保证： $1 \le n \le 1000$