AT_joig2025_b ポスター 2 (Poster 2)

JOI 学园的理惠同学制作了一张将于 $3$ 月举办的文化节的海报。这张海报由 $N$ 行 $N$ 列的格子组成，每个格子被涂上了 $K$ 种颜色中的一种，颜色编号为 $1$ 到 $K$。具体地说，从上到下第 $i$ 行，从左到右第 $j$ 列的格子（$1 \leq i \leq N$, $1 \leq j \leq N$）被涂上了颜色 $A_{i, j}$。 不过，在学生们讨论后，有人提出应该让海报更有色彩。具体地，大家觉得应该提高如下定义的「多彩度」。 - 多彩度：在所有连续的 $2$ 行 $2$ 列的正方形区域中，包含 $3$ 种或以上不同颜色的区域的数量。 例如，下图左为某张制作的海报，下图右边两个矩形区域均包含 $3$ 种以上的颜色，因此多彩度为 $2$。  提交海报的截止日期只剩下几分钟，为了最大化多彩度，你最多只能进行如下操作 $0$ 次或者 $1$ 次： - 任选一个格子，将其颜色任意更改为 $K$ 种颜色中的任意一种。 给出理惠同学一开始制作的海报内容，请编程求出经过至多一次操作后可以达到的最大多彩度。

输入格式如下： > $N$ $K$ $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}$

输出一个整数，表示可以达到的最大多彩度。

## 子任务 1. （$9$ 分）$N = 2$，$K = 3$。 2. （$6$ 分）所有 $A_{i, j}$（$1 \leq i \leq N$，$1 \leq j \leq N$）均互不相同。 3. （$27$ 分）$N \leq 10$，$K \leq 10$。 4. （$26$ 分）$N \leq 10$。 5. （$32$ 分）无额外约束。 ## 样例解释1 如下图，如果将第 $2$ 行第 $2$ 列（从上到下数、从左到右数）更改为颜色 $3$，则多彩度可达到 $1$。  无法达到多彩度 $2$ 或以上，因此输出 $1$。 本输入满足子任务 $1, 3, 4, 5$ 的约束。 ## 样例解释2 如下图，将第 $2$ 行第 $3$ 列的格子更改为颜色 $4$，可达到多彩度 $5$。  无法达到多彩度 $6$ 或以上，因此输出 $5$。 本输入满足子任务 $3, 4, 5$ 的约束。 ## 样例解释3 本输入满足子任务 $2, 4, 5$ 的约束。 ## 样例解释4 本输入满足子任务 $3, 4, 5$ 的约束。 ## 样例解释5 本输入满足子任务 $4, 5$ 的约束。 ## 约束条件 - $2 \leq N \leq 270$。 - $3 \leq K \leq 10^9$。 - $1 \leq A_{i, j} \leq K$（$1 \leq i \leq N$，$1 \leq j \leq N$）。 - 所有输入均为整数。 由 ChatGPT 5 翻译