网格染色 2

题目描述

有一个 $N\times N$ 的网格,每个格子里写着一个 $0$ 到 $5$ 之间的整数(含两端)。 设 $(i,j)$ 表示从上数第 $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}$。 网格的代价定义为相邻格子中写着的整数之差的平方和。即,代价由以下公式表示:

$\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

给定的网格如下所示:

进行操作达到右图所示的状态后,代价为 $2^2\times6+1^2\times18+0^2\times16=42$。

代价不可能小于或等于 $41$,因此输出该状态对应的 $B _ {i,j}$ 会被判定为正确。

3
0 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 \leq 20$
• $0 \leq A _ {i,j} \leq 5\ (1 \leq i \leq N,1 \leq j \leq N)$
• 所有输入值均为整数。

提示

答案不唯一,输出任意合法解即可。