题目描述

JOI 庭园呈正方形，被划分为 $N$ 行 $N$ 列的网格状区域。从上往下第 $i$ 行（$1 \le i \le N$）、从左往右第 $j$ 列（$1 \le j \le N$）的格子称为区域 $(i, j)$。

由于 JOI 庭园的土壤贫瘠，每个区域最多只能种植一种颜色的花，且最多只能种一棵。具体来说，区域 $(i, j)$ 中，当 $A_{i,j} = \text{R}$ 时只能种植红色花，当 $A_{i,j} = \text{Y}$ 时只能种植黄色花，当 $A_{i,j} = \text{B}$ 时只能种植蓝色花，且每个区域最多只能种一棵花。

现在，庭园的管理者 K 理事长希望在航拍时获得更好的视觉效果，因此计划按以下步骤种植花：

1. 确定一个表示大小的整数 $r$，需满足 $0 \le r \le (N-1) \div 2$。
2. 确定一个表示中心的区域 $(x, y)$，需满足 $r+1 \le x \le N-r$ 且 $r+1 \le y \le N-r$。
3. 从红、黄、蓝三种颜色中分别选择颜色 $c_0, c_1, c_2, \cdots, c_r$。
4. 对于每个区域 $(x', y')$，根据 $d = |x' - x| + |y' - y|$ 按以下规则种植花。其中，$|t|$ 表示 $t$ 的绝对值：
   • 若 $d \le r$，则在区域 $(x', y')$ 种植颜色为 $c_d$ 的花。
   • 若 $d > r$，则不在区域 $(x', y')$ 种植花。

给定庭园的大小，以及每个区域可种植的花的颜色信息，编写一个程序，求出 K 理事长最多能种植的花的数量。

输入格式

输入以如下格式给出：

$N$

$A_{1,1}\ A_{1,2}\ \cdots\ A_{1,N}$

$A_{2,1}\ A_{2,2}\ \cdots\ A_{2,N}$

$\vdots$

$A_{N,1}\ A_{N,2}\ \cdots\ A_{N,N}$

输出格式

输出一行，表示 K 理事长最多能种植的花的数量。

3
RYR
YBY
BYY

5

9
YYRYBBBYR
BYYRRBYBB
RBRRBRBBY
RYRBRYRBR
YYBRYYYRB
RRYBRYRBR
RBYRBRBRB
BRYYRBBBR
RBBBYBRRY

25

6
RBYRBY
BYRBYR
YRBYRB
RBYRBY
BYRBYR
YRBYRB

1

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

85

10
RRRRRRRRRR
RYRRRRRRRR
RRRRYRRRRR
RBRRRRRRRR
RRRRRRRRYR
RBRRRRRRRR
RRRRBRRRRR
RBRRRRRRRR
RRRRRRRRYR
RRRRRRRRRR

25

提示

样例 1 解释

若取 $r = 1$，中心 $(x, y) = (2, 2)$，并选择 $c_0$ 为蓝色、$c_1$ 为黄色，则可如图所示种植 5 朵花。图中背景色表示各区域可种植的花的颜色。

不存在能种植 6 朵或更多花的方法，因此输出 5。

该输入样例满足子任务 1、2、3、6 的约束。

:::align{center} :::

样例 2 解释

若取 $r = 3$，中心 $(x, y) = (5, 6)$，并选择 $c_0$ 为黄色、$c_1$ 为黄色、$c_2$ 为红色、$c_3$ 为蓝色，则可如图所示种植 25 朵花。图中背景色表示各区域可种植的花的颜色。

不存在能种植 26 朵或更多花的方法，因此输出 25。

该输入样例满足子任务 2、3、6 的约束。

:::align{center} :::

数据范围

• $3 \le N \le 3\,500$。
• $A_{i,j}$ 为 R、Y、B 中的某一个（$1 \le i \le N$，$1 \le j \le N$）。
• $N$ 为整数。

子任务

1. （4 分）$N = 3$。
2. （13 分）$N \le 50$。
3. （17 分）$N \le 800$。
4. （14 分）满足 $A_{i,j} \ne \text{R}$ 的 $(i, j)$（$1 \le i \le N$，$1 \le j \le N$）不超过 5 个。
5. （16 分）对于任意 $(i, j)$（$1 \le i \le N-1$，$1 \le j \le N-1$），在 $A_{i,j}$、$A_{i,j+1}$、$A_{i+1,j}$、$A_{i+1,j+1}$ 中，R 至少出现 3 次。
6. （36 分）无额外约束。

翻译由 Qwen3-235B 完成。