分数: 600 点
问题陈述
有一个网格 N 行和 N 列。让 (i, j) 表示位于 i从顶部开始的第行和 j左起第 列。
每个单元格包含一个整数。最初,细胞 (i,j) 包含整数 A_{i,j}.
您可以重复执行以下操作:
- 选择整数 i 和 j 这样 1\leq i, j\leq N 和一个整数 x,并添加 x to A_{i,j}。该操作的成本是 |x|.
给你一个正整数 d。您的目标是满足以下条件:
- 任意两个垂直或水平相邻的单元格中写入的整数之间的差至少为 d。更正式地说,满足以下两个条件:
- |A_{i,j}-A_{i+1,j}|\geq d 对于所有整数 i 和 j 这样 1\leq i\leq N-1 和 1\leq j\leq N.
- |A_{i,j}-A_{i,j+1}|\geq d 对于所有整数 i 和 j 这样 1\leq i\leq N 和 1\leq j\leq N-1.
实现这一目标的总成本为 \frac12 dN^2 或更少。
约束
- 2\leq N\leq 500
- 1\leq d\leq 1000
- -1000\leq A_{i,j}\leq 1000
输入
输入由标准输入按以下格式给出:
N d
A_{1,1} \cdots A_{1,N}
\vdots
A_{N,1} \cdots A_{N,N}
输出
按照以下格式打印一系列操作后网格的状态:
A_{1,1} \cdots A_{1,N}
\vdots
A_{N,1} \cdots A_{N,N}
如果多个网格状态满足条件,则其中任何一个都将被接受。无需最小化总成本。
示例输入 1
3 5 -2 1 3 3 -4 -4 0 1 3
示例输出 1
-2 8 3 3 -9 -4 -2 8 3
执行四次如下操作以生成示例输出中所示的网格:
- 执行操作 (i,j,x)=(1,2,7).
- 执行操作 (i,j,x)=(2,2,-5).
- 执行操作 (i,j,x)=(3,1,-2).
- 执行操作 (i,j,x)=(3,2,7).
总成本为 7+5+2+7=21,不大于 \frac{1}{2}dN^2=\frac{45}{2}.
示例输入 2
5 2 1 5 5 0 3 2 0 2 5 1 5 2 0 5 5 3 7 2 0 1 6 0 4 3 6
示例输出 2
0 4 6 1 3 3 1 3 6 1 5 3 0 3 5 2 6 3 1 3 4 0 5 3 6