A - Adjacent Difference Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 行 N 列のマス目があります．上から i 行目，左から j 列目のマスをマス (i,j) と表します．

各マスには整数がひとつずつ書き込まれており，はじめマス (i,j) に書き込まれている整数は A_{i,j} です．

あなたは次の操作を繰り返し行うことができます：

  • 1\leq i, j\leq N を満たす整数 i,j および整数 x を選び，A_{i,j} に x を加える．この操作にはコストが |x| かかる．

正整数 d が与えられます．あなたの目標は次の条件が成り立つようにすることです：

  • 上下左右の 4 方向に隣接する 2 マスに書き込まれている整数の差は d 以上である．より形式的には，次の 2 条件が成り立つ：
    • 1\leq i\leq N-1, 1\leq j\leq N を満たす整数 i, j に対して |A_{i,j}-A_{i+1,j}|\geq d．
    • 1\leq i\leq N, 1\leq j\leq N-1 を満たす整数 i, j に対して |A_{i,j}-A_{i,j+1}|\geq d．

この目標を，総コスト \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

次のように 4 回の操作を行うと，マス目の状態が出力例の通りになります．

  • (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

Score: 600 points

Problem Statement

There is a grid with N rows and N columns. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.

Each cell contains an integer. Initially, cell (i,j) contains the integer A_{i,j}.

You can repeatedly perform the following operation:

  • Choose integers i and j such that 1\leq i, j\leq N and an integer x, and add x to A_{i,j}. The cost of this operation is |x|.

You are given a positive integer d. Your goal is to satisfy the following condition:

  • The difference between the integers written in any two cells that are vertically or horizontally adjacent is at least d. More formally, the following two conditions are satisfied:
    • |A_{i,j}-A_{i+1,j}|\geq d for all integers i and j such that 1\leq i\leq N-1 and 1\leq j\leq N.
    • |A_{i,j}-A_{i,j+1}|\geq d for all integers i and j such that 1\leq i\leq N and 1\leq j\leq N-1.

Achieve this goal with a total cost of \frac12 dN^2 or less.

Constraints

  • 2\leq N\leq 500
  • 1\leq d\leq 1000
  • -1000\leq A_{i,j}\leq 1000

Input

The input is given from Standard Input in the following format:

N d
A_{1,1} \cdots A_{1,N}
\vdots
A_{N,1} \cdots A_{N,N}

Output

Print the state of the grid after the series of operations in the following format:

A_{1,1} \cdots A_{1,N}
\vdots
A_{N,1} \cdots A_{N,N}

If multiple grid states satisfy the condition, any of them will be accepted. There is no need to minimize the total cost.

Sample Input 1

3 5
-2 1 3
3 -4 -4
0 1 3

Sample Output 1

-2 8 3
3 -9 -4
-2 8 3

Perform the operation four times as follows to yield the grid shown in the sample output:

  • Perform the operation with (i,j,x)=(1,2,7).
  • Perform the operation with (i,j,x)=(2,2,-5).
  • Perform the operation with (i,j,x)=(3,1,-2).
  • Perform the operation with (i,j,x)=(3,2,7).

The total cost is 7+5+2+7=21, which is not greater than \frac{1}{2}dN^2=\frac{45}{2}.

Sample Input 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

Sample Output 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