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