G - Grid Coloring 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N\times N のマス目があり、それぞれのマスには 0 以上 5 以下の整数が書かれています。 上から i 行目、左から j 列目 (1\leq i,j\leq N) のマスをマス (i,j) と表し、マス (i,j) には整数 A _ {i,j} が書かれています。

このマス目に対して、次の操作を 0 回以上好きな回数行います。

  • 0 が書かれているマス (i,j) と 1 以上 5 以下の整数 x を 1 つ選ぶ。選ばれたマスに書かれている数を x に変更する。

操作が終了したあと、マス (i,j) に書かれている整数を B _ {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

Score: 600 points

Problem Statement

There is an N\times N grid where each cell contains an integer between 0 and 5, inclusive. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left (1\leq i,j\leq N). The integer written in cell (i,j) is A _ {i,j}.

You can perform the following operation any number of times, possibly zero:

  • Choose a cell (i,j) with 0 written in it and an integer x between 1 and 5, inclusive. Change the number written in the chosen cell to x.

After the operations, let B _ {i,j} be the integer written in cell (i,j). The cost of the grid is defined as the sum of the squares of the differences between the integers written in adjacent cells. In other words, the cost is represented by the following formula:

\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

Among all possible states of the grid after the operations, find the one with the minimum cost.

If multiple grid states have the minimum cost, you may print any of them.

Constraints

  • 1\leq N\leq20
  • 0\leq A _ {i,j}\leq 5\ (1\leq i\leq N,1\leq j\leq N)
  • All input values are integers.

Input

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

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}

Output

Print N lines. The i-th line (1\leq i\leq N) should contain B _ {i,1},B _ {i,2},\ldots,B _ {i,N} in this order, with spaces in between, after performing operations to minimize the cost.

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

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

The given grid is as follows:

After performing operations to achieve the state shown on the right of the figure, the cost will be 2 ^ 2\times6+1 ^ 2\times18+0 ^ 2\times16=42.

The cost cannot be 41 or less, so printing the corresponding B _ {i,j} for this state would be accepted.

Sample Input 2

3
0 0 0
0 0 0
0 0 0

Sample Output 2

0 0 0
0 0 0
0 0 0

The cost is already 0 from the beginning, so not performing any operations minimizes the cost.

If multiple grid states have the minimum cost, you may print any of them, so the following output would also be accepted:

2 2 2
2 2 2
2 2 2

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

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