← 返回题目列表

AtCoder · abc347_g

G. 网格着色 2

中文机器翻译题面 查看原题

分数: 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)。 的 网格的 成本 一次操作的 被定义为相邻单元格中写入的整数之间的差的平方和。换句话说,成本由以下公式表示:

\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

在操作后网格的所有可能状态中,找到成本最小的状态。

如果多个网格状态具有最小成本,则可以打印其中任何一个。

约束

  • 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