Grid Coloring 2

题目描述

有一个 $N\times N$ 的网格，每个格子中写有一个介于 $0$ 到 $5$（含）之间的整数。 记 $(i,j)$ 为从上数第 $i$ 行、从左数第 $j$ 列的格子 $(1\leq i,j\leq N)$。格子 $(i,j)$ 中写的整数为 $A _ {i,j}$。 你可以任意次（也可以为零次）执行以下操作：

选择一个写有 $0$ 的格子 $(i,j)$ 和一个介于 $1$ 到 $5$（含）之间的整数 $x$。将被选格子中写的数改为 $x$。

在所有操作之后，令 $B _ {i,j}$ 为格子 $(i,j)$ 中最终写的整数。 该网格的代价被定义为相邻格子所写整数差的平方和。换言之，代价由下式表示：

$\displaystyle\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$ $\ \vdots$ $\ddots$ $\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}$（以此顺序），数字之间以空格分隔。

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

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

3
0 0 0
0 0 0
0 0 0

0 0 0
0 0 0
0 0 0

2 2 2
2 2 2
2 2 2

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

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\leq20$ $0\leq A _ {i,j}\leq 5\ (1\leq i\leq N,1\leq j\leq N)$ 所有输入值均为整数。给定的网格如下所示： 经过操作得到图中右侧所示的状态后，代价为 $2 ^ 2\times6+1 ^ 2\times18+0 ^ 2\times16=42$。 代价不可能为 $41$ 或更小，所以输出对应该状态的 $B _ {i,j}$ 将被接受。
代价从一开始就是 $0$，因此不进行任何操作就已使代价最小化。 如果存在多个代价最小的网格状态，你可以输出其中任意一个，所以下面的输出也将被接受：

标签: AtCoder|abc347G

来源

AtCoder|abc347G