← 返回题目列表

Codeforces · 1986/B

B. 矩阵稳定

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

给定一个大小为 $$$n \times m$$$ 的矩阵,其中行从上到下编号为 $$$1$$$ 到 $$$n$$$,列从左到右编号为 $$$1$$$ 到 $$$m$$$。第 $$$i$$$ 行和第 $$$j$$$ 列交叉处的元素由 $$$a_{ij}$$$ 表示。

考虑稳定矩阵$$$a$$$的算法:

1. 找到单元格$$$(i, j)$$$,使其值严格大于其所有相邻单元格的值。如果不存在这样的单元,则终止算法。如果有多个这样的单元格,则选择$$$i$$$ 值最小的单元格,如果还有多个单元格,则选择$$$j$$$ 值最小的单元格。
2. 设置 $$$a_{ij} = a_{ij} - 1$$$。
3. 转到步骤$$$1$$$。

在此问题中,单元格 $$$(a, b)$$$ 和 $$$(c, d)$$$ 如果共享公共边,则被视为邻居,即 $$$|a - c| + |b - d| = 1$$$。

您的任务是在执行稳定算法后输出矩阵$$$a$$$。可以证明该算法不能运行无限次迭代。

输入

每个测试由多组输入数据组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 输入数据的组数。接下来是他们的描述。

每组输入数据的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 100, n \cdot m > 1$$$) — 矩阵 $$$a$$$ 的行数和列数。

接下来的 $$$n$$$ 行描述了矩阵的相应行。第 $$$i$$$ 行包含 $$$m$$$ 整数 $$$a_{i1}, a_{i2}, \ldots, a_{im}$$$ ($$$1 \leq a_{ij} \leq 10^9$$$)。

保证所有输入数据集的 $$$n \cdot m$$$ 之和不超过 $$$2 \cdot 10^5$$$。

输出

对于每组输入数据,输出 $$$n$$$ 行,每行包含 $$$m$$$ 个数字 - 稳定算法后矩阵 $$$a$$$ 的单元格值。

示例

输入 #1

6
1 2
3 1
2 1
1
1
2 2
1 2
3 4
2 3
7 4 5
1 8 10
5 4
92 74 31 74
74 92 17 7
31 17 92 3
74 7 3 92
7 31 1 1
3 3
1000000000 1 1000000000
1 1000000000 1
1000000000 1 1000000000

输出 #1

1 1 
1 
1 
1 2 
3 3 
4 4 5 
1 8 8 
74 74 31 31 
74 74 17 7 
31 17 17 3 
31 7 3 3 
7 7 1 1 
1 1 1 
1 1 1 
1 1 1

注意

在第一组输入数据中,算法将连续选择单元格 $$$(1, 1)$$$ 两次,然后终止。

在第二组输入数据中,不存在其值严格大于所有相邻像元的值的像元。

在第三组输入数据中,算法将选择单元格 $$$(2, 2)$$$,然后终止。

在第四组输入数据中,算法将选择单元格 $$$(1, 1)$$$ 三次,然后选择单元格 $$$(2, 3)$$$ 两次。