← 返回题目列表

Codeforces · 1375/B

B. 邻居网格

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

为您提供一个包含 $$$n$$$ 行和 $$$m$$$ 列的网格,其中每个单元格上都写有一个非负整数。如果对于每个单元格满足以下条件,我们就说网格是好的:如果它上面写有数字 $$$k > 0$$$,那么其相邻单元格中恰好 $$$k$$$ 上写有大于 $$$0$$$ 的数字。注意,如果单元格中的数字是$$$0$$$,则相邻单元格没有这样的限制。

您可以在网格中取任何数字并将其增加$$$1$$$。您可以对任意数字多次应用此操作。执行一些操作(可能是零)可以让网格变好,或者说不可能。如果有多个可能的答案,您可能会找到其中任何一个。

如果两个小区具有共同边缘,则它们被视为相邻小区。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n, m \le 300$$$) — 分别是行数和列数。

以下 $$$n$$$ 行每行包含 $$$m$$$ 个整数,$$$i$$$ 第 $$$a_{i, j}$$$ 行中的第 $$$j$$$ 元素是第 $$$i$$$ 行第 $$$j$$$ 单元格中写入的数字 ($$$0 \le a_{i, j} \le 10^9$$$)。

保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$10^5$$$。

输出

如果无法获得良好的网格,则打印包含“NO”的单行。

否则,打印包含“YES”的单行,后跟 $$$n$$$ 行,每行包含 $$$m$$$ 整数,这些整数描述网格的最终状态。这个最终网格应该可以通过应用一些操作(可能为零)从初始网格获得。

如果有多个可能的答案,您可以打印其中任何一个。

示例

输入 #1

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

输出 #1

YES
0 0 0 0
0 1 1 0
0 0 0 0
NO
YES
0 0
0 0
NO
YES
0 1 0 0
1 4 2 1
0 2 0 0
1 3 1 0

注意

在第一个测试用例中,我们可以通过将行$$$2$$$、列$$$3$$$中的数字增加一次来获得结果网格。包含 $$$1$$$ 的两个单元格都恰好有一个大于零的邻居,因此网格良好。存在许多其他解决方案,例如网格

$$$$$$0\;1\;0\;0$$$$$$ $$$$$$0\;2\;1\;0$$$$$$ $$$$$$0\;0\;0\;0$$$$$$

所有这些都被视为有效答案。

在第二个测试用例中,不可能使网格良好。

在第三个测试用例中,请注意没有单元格上的数字大于零,因此网格自动良好。