[ABC347] G - Grid Coloring 2

G - Grid Coloring 2

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 分

题面

有一个 的网格，每个格子中包含一个 到 的整数，包括 和 。记 为位于从上往下第 行、从左到右第 列的格子 。格子 中的整数为 。

你可以进行任意次以下操作（可能为 次）：

• 选择一个整数为 的格子 ，选择一个介于 到 之间的整数 。将选定的格子中的数字修改为 。

在进行操作之后，设 为格子 中的整数。网格的代价定义为相邻格子中整数差的平方和。换句话说，代价可以用下面的公式表示：

在所有可能的操作后的网格状态中，找出代价最小的状态。

如果有多个网格状态具有最小代价，你可以输出其中任意一个。

限制条件

• 所有输入值都是整数。

---

输入

从标准输入读入以下格式的输入。

输出

将最小化代价后的网格状态按行输出，第 行（）依次包含 ，各个数之间用空格隔开。

---

输入样例 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

3
0 0 0
0 0 0
0 0 0

输出样例 2

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