AT_abc347_g [ABC347G] Grid Coloring 2

题目描述

有一个 $N\times N$ 的网格，每个格子上写有一个 $0$ 到 $5$ 之间的整数。第 $i$ 行第 $j$ 列的格子（$1\leq i,j\leq N$）记作格子 $(i,j)$，其中写着整数 $A_{i,j}$。

你可以对这个网格进行任意次如下操作（可以为 $0$ 次）：

• 选择一个写着 $0$ 的格子 $(i,j)$，以及一个 $1$ 到 $5$ 之间的整数 $x$，将该格子上的数改为 $x$。

操作结束后，格子 $(i,j)$ 上的整数记作 $B_{i,j}$。定义网格的代价为所有相邻格子上的整数差的平方和。即，代价由下式给出：

$$\sum_{i=1}^N\sum_{j=1}^{N-1}(B_{i,j}-B_{i,j+1})^2+\sum_{i=1}^{N-1}\sum_{j=1}^N(B_{i,j}-B_{i+1,j})^2$$

请你求出所有可能的操作结束后的网格中，代价最小的一个。

如果有多个代价最小的网格状态，输出其中任意一个即可。

输入格式

输入按以下格式从标准输入给出。

$N$ $A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,N}$ $A_{2,1}$ $A_{2,2}$ $\ldots$ $A_{2,N}$
$\vdots$
$A_{N,1}$ $A_{N,2}$ $\ldots$ $A_{N,N}$

输出格式

输出 $N$ 行。第 $i$ 行（$1\leq i\leq N$）输出操作后使代价最小的 $B_{i,1},B_{i,2},\ldots,B_{i,N}$，用空格分隔。

输入输出样例 #1

输入 #1

5
0 2 1 0 4
4 0 0 0 2
3 1 0 3 0
1 0 0 0 0
0 0 2 0 5

输出 #1

3 2 1 2 4
4 2 2 2 2
3 1 2 3 3
1 1 2 3 4
1 1 2 3 5

输入输出样例 #2

输入 #2

3
0 0 0
0 0 0
0 0 0

输出 #2

0 0 0
0 0 0
0 0 0

输入输出样例 #3

输入 #3

10
1 0 0 3 0 0 0 0 0 0
1 0 0 4 0 1 0 5 0 0
0 0 0 0 0 0 2 0 3 0
0 0 2 0 0 0 4 0 0 3
0 3 4 3 3 0 3 0 0 5
4 1 3 4 4 0 2 1 0 0
2 0 1 0 5 2 0 1 1 5
0 0 0 5 0 0 3 2 4 0
4 5 0 0 3 2 0 3 5 0
4 0 0 5 0 0 0 3 0 5

输出 #3

1 2 3 3 3 2 3 4 4 4
1 2 3 4 3 1 3 5 4 4
2 2 2 3 3 2 2 3 3 3
2 2 2 3 3 3 4 3 3 3
3 3 4 3 3 3 3 2 3 5
4 1 3 4 4 3 2 1 2 4
2 2 1 4 5 2 2 1 1 5
3 3 3 5 4 3 3 2 4 5
4 5 4 4 3 2 3 3 5 5
4 4 4 5 4 3 3 3 4 5

说明/提示

限制条件

• $1\leq N\leq 20$
• $0\leq A_{i,j}\leq 5\ (1\leq i\leq N,1\leq j\leq N)$
• 输入均为整数

样例解释 1

给定的网格如下所示。

通过将网格变为右图的状态，代价为 $2^2\times6+1^2\times18+0^2\times16=42$。
无法使代价小于 $41$，因此输出对应的 $B_{i,j}$ 即为正确答案。

样例解释 2

初始状态的代价已经为 $0$，因此不进行操作即可达到最小代价。
由于操作结束后的网格状态中有多个代价最小的情况，输出如下也可以：

2 2 2
2 2 2
2 2 2

由 ChatGPT 4.1 翻译