#5757. 「ROI 2026 Day2」广义象棋

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

译自 ROI 2026 Day2 T1. Обобщённые шахматы

Mikhail 决定学习如何玩广义象棋，为此他准备了一个 $n \times n$ 大小的棋盘。他将位于第 $i$ 行和第 $j$ 列交汇处的单元格涂上了颜色 $a_{i j}$。

Mikhail 还是个初学者，他可能会把棋盘涂错颜色。因此，棋盘上的某些单元格可能需要重新涂上另一种颜色。如果满足以下两个条件，则认为棋盘是正确着色的：

• 棋盘上的单元格涂有的颜色种类不超过两种；
• 棋盘上不存在边相邻且颜色相同的单元格。

Mikhail 觉得在太大的棋盘上玩对他来说太难了。因此，他可能会从现有的棋盘中截取一个较小的区域，只保留由前 $r$ 行和前 $c$ 列组成的矩形区域，并只要求这个区域是正确着色的。

对于每一对整数 $r$ 和 $c$ $(1 \leq r \leq n, 1 \leq c \leq n)$，请计算出 $b_{r c}$ 的值，即为了使棋盘中由前 $r$ 行和前 $c$ 列组成的矩形区域达到正确着色，Mikhail 最少需要重新涂色的单元格数量。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 400)$，表示棋盘的大小。

接下来的 $n$ 行描述了棋盘的初始颜色：其中第 $i$ 行包含 $n$ 个整数 $a_{i 1}, \dots, a_{i n}$ $(1 \leq a_{i j} \leq 10^9)$，分别表示棋盘第 $i$ 行各单元格的颜色。

输出格式

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

样例 1

输入

2
7 7
7 7

输出

0 1
1 2

样例 2

输入

3
1 1 2
2 4 4
3 1 2

输出

0 1 1
0 2 4
1 3 5

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。