AT_joi2024_yo2_d.庭園 2 (Garden 2)

JOI 庭园是一个被划分为纵向 $N$ 行、横向 $N$ 列格子的正方形区域。从上往下的第 $i$ 行（$1 \leq i \leq N$）、从左往右的第 $j$ 列（$1 \leq j \leq N$）的格子称为区块 $(i, j)$。

由于 JOI 庭园的土壤条件有限，每个区块仅能种植最多一株、且只能种植一种特定颜色的花。具体来说，若区块 $(i, j)$ 的 $A_{i, j} = $ R，则只能种植红色花；若 $A_{i, j} = $ Y，则只能种植黄色花；若 $A_{i, j} = $ B，则只能种植蓝色花，每个区块至多只能种植一种颜色的花。

庭园的管理者 K 理事长为了让航空摄影看起来更美观，计划按照如下流程来种花：

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

给定庭园的大小 $N$ 以及每个区块可以种植的花的颜色，请编写程序，求出 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 理事长最多能种植的花的数量，仅一行。

子任务

1.（4 分）$N = 3$。

2.（13 分）$N \leq 50$。

3.（17 分）$N \leq 800$。

4.（14 分）满足 $A_{i, j} \ne$ R 的 $(i, j)$（$1 \leq i \leq N, 1 \leq j \leq N$）至多只有 5 个。

5.（16 分）对于所有 $(i, j)$（$1 \leq i \leq N-1, 1 \leq j \leq N-1$），$A_{i, j}$，$A_{i, j+1}$，$A_{i+1, j}$，$A_{i+1, j+1}$ 中至少有 3 个为 R。

6.（36 分）无额外限制。

样例解释 1

取 $r=1$，$(x, y) = (2, 2)$，$c_0$ 选蓝色，$c_1$ 选黄色时，可以如下种植 5 朵花。背景色表示每个区块可种植的花色。

没有办法种植 6 朵及以上的花，所以输出 $5$。

该输入数据满足子任务 1, 2, 3, 6 的约束。

样例解释 2

取 $r=3$，$(x, y) = (5, 6)$，$c_0$ 选黄色，$c_1$ 选黄色，$c_2$ 选红色，$c_3$ 选蓝色，此时可以如下种植 25 朵花。背景色表示每个区块可种植的花色。

没有办法种植 26 朵及以上的花，所以输出 $25$。

该输入数据满足子任务 2, 3, 6 的约束。

样例解释 3

此输入满足子任务 2，3，6 的约束。

样例解释 4

此输入满足子任务 2，3，4，5，6 的约束。

样例解释 5

此输入满足子任务 2，3，5，6 的约束。

约束条件

• $3 \leq N \leq 3500$。
• $A_{i, j}$ 只可能为 R、Y、B 中之一（$1 \leq i \leq N, 1 \leq j \leq N$）。
• $N$ 为整数。

由 ChatGPT 5 翻译