P17022 [ROI 2026 Day2] 广义象棋

米哈伊尔决定学习下广义象棋，为此他准备了一个大小为 $n \times n$ 的棋盘。他将第 $i$ 行第 $j$ 列的格子涂成了颜色 $a_{i j}$。 米哈伊尔是个新手，他可能把棋盘涂错了。因此，棋盘上的某些格子可能需要重新涂成另一种颜色。一个棋盘被称为**正确涂色**，当且仅当同时满足以下两个条件： - 棋盘上的格子至多使用两种不同颜色； - 棋盘上不存在边相邻且颜色相同的格子。 米哈伊尔考虑到，在太大的棋盘上对局会过于困难。因此，他可能会从自己的棋盘上裁出一个较小的棋盘，即保留前 $r$ 行和前 $c$ 列构成的矩形区域，并只将这一部分正确涂色。 对于每一对数 $r$ 和 $c$（$1 \le r \le n$，$1 \le c \le n$），请计算 $b_{r c}$ 的值——使得由前 $r$ 行和前 $c$ 列构成的矩形区域变为正确涂色，米哈伊尔最少需要重新涂色的格子数目。

第一行包含一个整数 $n$（$1 \le n \le 400$），表示棋盘的大小。 接下来的 $n$ 行描述棋盘：其中第 $i$ 行包含 $n$ 个整数 $a_{i 1}, \ldots, a_{i n}$（$1 \le a_{i j} \le 10^9$），表示棋盘第 $i$ 行各个格子的颜色。

输出 $n$ 行，其中第 $i$ 行应包含 $n$ 个整数 $b_{i 1}, \ldots, b_{i n}$。

### 子任务 | 子任务 | 分数 | $n$ | $a_{i j}$ | 依赖子任务 | |:---:|:---:|:---:|:---:|:---:| | 1 | 11 | $n \le 50$ | -- | | | 2 | 22 | $n \le 200$ | -- | 1 | | 3 | 8 | -- | $a_{i j} \le 2$ | -- | | 4 | 17 | -- | $a_{i j} \le 10$ | 3 | | 5 | 15 | -- | $a_{i j} \le 100$ | 3–4 | | 6 | 7 | -- | $a_{i j} \le 10^4$ | 3–5 | | 7 | 20 | -- | -- | 1–6 | 翻译由 DeepSeek V4 Pro 完成