分数: 600 点
问题陈述
有一个 N\times N 网格,其中每个单元格包含一个介于 0 和 5,包括在内。 让 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列 (1\leq i,j\leq N)。单元格中写入的整数 (i,j) is A _ {i,j}.
您可以执行以下操作任意次数,可能为零:
- 选择一个单元格 其中写入 (i,j) 与 0 和一个整数 x 之间 1 和 5,包括在内。将所选单元格中写入的数字更改为 x.
运算后,让 B _ {i,j} 是写入单元格的整数 (i,j)。 的 网格的 成本 一次操作的 被定义为相邻单元格中写入的整数之间的差的平方和。换句话说,成本由以下公式表示:
在操作后网格的所有可能状态中,找到成本最小的状态。
如果多个网格状态具有最小成本,则可以打印其中任何一个。
约束
- 1\leq N\leq20
- 0\leq A _ {i,j}\leq 5\ (1\leq i\leq N,1\leq j\leq N)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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} 按照此顺序,在执行操作后将其之间留有空格以最小化成本。
示例输入 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\times6+1 ^ 2\times18+0 ^ 2\times16=42.
成本不能 41 或更少,因此打印相应的 此状态的 B _ {i,j} 将被接受。
示例输入 2
3 0 0 0 0 0 0 0 0 0
示例输出 2
0 0 0 0 0 0 0 0 0
成本已 0 从一开始,因此不执行任何操作可以最大限度地降低成本。
如果多个网格状态具有最小成本,您可以打印其中任何一个,因此以下输出也将被接受:
2 2 2 2 2 2 2 2 2
示例输入 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