103476: [Atcoder]ABC347 G - Grid Coloring 2
Description
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:
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
Input
Output
得分：600分
问题描述
有一个$N\times N$的网格，其中每个单元格都包含一个介于$0$和$5$之间的整数，包括$0$和$5$。 让$(i,j)$表示从上数第$i$行、从左数第$j$列的单元格 $(1\leq i,j\leq N)$。该单元格中书写的整数是$A _ {i,j}$。
你可以执行任意次数的操作，包括零次：
- 选择一个包含$0$的单元格$(i,j)$和一个介于$1$和$5$之间的整数$x$。将所选单元格中的数字改为$x$。
操作完成后，让$B _ {i,j}$表示单元格$(i,j)$中的整数。 网格的 成本 是相邻单元格中书写的整数之差的平方之和。换句话说，成本由以下公式表示：
在操作后所有可能的网格状态中，找到具有最小成本的那个。
如果有多个网格状态具有最小成本，你可以打印其中任何一个。
约束
- $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