P14295 [JOI2024 预选赛 R2] 花园 2 / Garden 2

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 理事长最多能种植的花的数量。

### 样例 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 完成。