花园2

时间限制： 4 秒 内存限制： 1048576 KB

问题描述

JOI 花园的形状是一个方形，被垂直和水平地分成了小方块。位于从顶部到第 i 行和从左到第 j 列的方块被称为 (i,j) 分区。

由于 JOI 花园的土壤并不十分丰富，因此每个方块上最多只能种植一定类型的花。具体而言，每个方块上最多只能种植一种颜色的红色、黄色和蓝色花朵。

这里，花园的管理员 Mr. K 计划按照以下步骤种植花朵，以改善航拍照片的外观：

1. 确定代表规模的整数 r，但必须满足 0 ≤ r ≤ (N−1)/2。

2. 确定代表中心的方块 (x,y)，但必须满足 r+1 ≤ x ≤ N−r 且 r+1 ≤ y ≤ N−r。

3. 从红色、黄色和蓝色中选择颜色 c0, c1, c2, ..., cr。

4. 对于每个方块 (x',y')，根据以下规则种植花朵，其中 d=|x'−x|+|y'−y| 代表绝对值：

   • 如果 d ≤ r，则在方块 (x',y') 上种植颜色为 cd 的花朵。
   • 如果 d > r，则不在方块 (x',y') 上种植花朵。

给定花园的大小和每个方块可以种植的花朵颜色的信息，编写程序确定可以种植的最大花朵数量。

约束条件

• 3 ≤ N ≤ 3500
• A_i,j 为 R, Y 或 B 中的一个字符
• N 是整数

输入

输入格式如下：

N
A1,1 A1,2 ... A1,N
A2,1 A2,2 ... A2,N
...
AN,1 AN,2 ... AN,N

输出

输出可以种植的最大花朵数量。

输入输出示例

输入示例 1

3
RYR
YBY
BYY

输出示例 1

5

r=1 如果选择 (x,y)=(2,2)，并选择蓝色和黄色作为颜色，则可以按照下图所示在分区中种植花朵，背景颜色表示每个分区可以种植的花朵颜色。

6 由于没有办法种植比书中更多的花朵，输出 5。

输入示例 2

9
YYRYBBBYR
BYYRRBYBB
RBRRBRBBY
RYRBRYRBR
YYBRYYYRB
RRYBRYRBR
RBYRBRBRB
BRYYRBBBR
RBBBYBRRY

输出示例 2

25

如果选择 r=3，并选择黄色、黄色、红色和蓝色作为颜色，那么可以按照下图所示在分区中种植花朵，背景颜色表示每个分区可以种植的花朵颜色。(x,y)=(5,6)

由于没有办法种植比书中更多的花朵，输出 25。

输入示例 3

6
RBYRBY
BYRBYR
YRBYRB
RBYRBY
BYRBYR
YRBYRB

输出示例 3

1

输入示例 4

20
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRBRRRRRRRRRRRRYRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRYRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRYRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRBR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR

输出示例 4

85

输入示例 5

10
RRRRRRRRRR
RYRRRRRRRR
RRRRYRRRRR
RBRRRRRRRR
RRRRRRRRYR
RBRRRRRRRR
RRRRBRRRRR
RBRRRRRRRR
RRRRRRRRYR
RRRRRRRRRR

输出示例 5

25

---