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\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 翻译