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 翻译