← 返回题目列表

AtCoder · agc066_a

A. 相邻差异

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

分数: 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