#11203. 花园2
花园2
花园2
时间限制: 4 秒 内存限制: 1048576 KB
问题描述
JOI 花园的形状是一个方形,被垂直和水平地分成了小方块。位于从顶部到第 i 行和从左到第 j 列的方块被称为 (i,j) 分区。
由于 JOI 花园的土壤并不十分丰富,因此每个方块上最多只能种植一定类型的花。具体而言,每个方块上最多只能种植一种颜色的红色、黄色和蓝色花朵。
这里,花园的管理员 Mr. K 计划按照以下步骤种植花朵,以改善航拍照片的外观:
-
确定代表规模的整数 r,但必须满足 0 ≤ r ≤ (N−1)/2。
-
确定代表中心的方块 (x,y),但必须满足 r+1 ≤ x ≤ N−r 且 r+1 ≤ y ≤ N−r。
-
从红色、黄色和蓝色中选择颜色 c0, c1, c2, ..., cr。
-
对于每个方块 (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