#1402. 海嗣模拟器

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Corycle

题目描述

罗德岛的干员们最近在玩一个很新的游戏:“海嗣模拟器”

游戏在一个由 个正方形格子组成的棋盘上进行,干员们可以在格子里召唤一只海嗣,并将自己的编号写在格子里来占有这个格子。

最终每个格子都包含一个数。每个干员可以选择一个被他占领的连通区域,并获得等于该连通区域大小的得分(他不一定会选择自己所占领的最大连通区域)。连通区域定义为一些具有相同数字编号的格子,并且其中每个在该连通区域的格子都直接与另一个同在该连通区域中的格子通过上、下、左或右相邻。

在游戏结束前,伊莎玛拉会降临这片大地,并随机为一位干员赋予“海嗣之力”,获得海嗣之力的干员可以吞噬一个他选择的区域的相邻连通区域,并获得等于被吞噬的连通区域大小的得分。

给定伊莎玛拉降临前棋盘的状态,请计算得分最大的干员可能获得的分数的最大值。

输入格式

第一行仅包含一个正整数 ,表示棋盘的大小。

接下来 行,每行有 个正整数,表示该格子的占有状态。

输出格式

一行仅一个正整数,表示最大分数。

样例

样例输入1

4
2 3 9 5
4 9 9 7
9 9 1 7
6 1 1 9

样例输出1

8

样例输入2

5
5 4 4 2 2 
2 1 5 5 5 
2 2 3 3 3 
1 2 3 1 1 
1 1 5 2 5 

样例输入2

8

数据范围与提示

数据保证 ,棋盘上至少有两中数字,且每个数字的大小在 之间