P17022 [ROI 2026 Day2] Generalized Chess

Mikhail decided to learn generalized chess, so he prepared a board of size $n \times n$. He painted the cell in row $i$ and column $j$ with color $a_{i j}$. Since Mikhail is a beginner, he may have painted the board incorrectly. Therefore, some cells on the board may need to be repainted to another color. A board is called **properly colored** if and only if it satisfies both of the following conditions: - The board uses at most two different colors in total. - There are no edge-adjacent cells with the same color. Mikhail also considers that playing on a board that is too large would be too difficult. Therefore, he may cut out a smaller board from his board, that is, keep the rectangle formed by the first $r$ rows and the first $c$ columns, and only make this part properly colored. For every pair $(r, c)$ ($1 \le r \le n$, $1 \le c \le n$), compute the value $b_{r c}$—the minimum number of cells Mikhail needs to repaint so that the rectangle formed by the first $r$ rows and the first $c$ columns becomes properly colored.

The first line contains an integer $n$ ($1 \le n \le 400$), which denotes the size of the board. The next $n$ lines describe the board: the $i$-th line contains $n$ integers $a_{i 1}, \ldots, a_{i n}$ ($1 \le a_{i j} \le 10^9$), representing the colors of the cells in row $i$ of the board.

Output $n$ lines, where the $i$-th line should contain $n$ integers $b_{i 1}, \ldots, b_{i n}$.

### Subtasks | Subtask | Score | $n$ | $a_{i j}$ | Dependencies | |:---:|:---:|:---:|:---:|:---:| | 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 | Translated by DeepSeek V4 Pro. Translated by ChatGPT 5