#11203. 花园2

花园2

花园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),并选择蓝色和黄色作为颜色,则可以按照下图所示在分区中种植花朵,背景颜色表示每个分区可以种植的花朵颜色。 image

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

输入示例 2

9
YYRYBBBYR
BYYRRBYBB
RBRRBRBBY
RYRBRYRBR
YYBRYYYRB
RRYBRYRBR
RBYRBRBRB
BRYYRBBBR
RBBBYBRRY

输出示例 2

25

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

由于没有办法种植比书中更多的花朵,输出 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