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