← 返回题目列表

Codeforces · 1738/G

G. 防上瘾者

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

给你一个 $$$n \times n$$$ 网格。

我们写 $$$(i, j)$$$ 来表示第 $$$i$$$ 行和 $$$j$$$ 列中的单元格。对于每个单元格,您都会被告知是否可以删除它。

给定一个整数 $$$k$$$,系统会要求您从网格中准确删除 $$$(n-k+1)^2$$$ 个单元格,以便满足以下条件。

- 您找不到 $$$k$$$ 未删除的单元格 $$$(x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)$$$ 严格递增,即 $$$x_i < x_{i+1}$$$ 和 $$$y_i < y_{i+1}$$$ $$$1 \leq i < k$$$。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。以下行包含每个测试用例的描述。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \leq k \leq n \leq 1000$$$)。

然后是 $$$n$$$ 行。第 $$$i$$$ 行包含长度为 $$$n$$$ 的二进制字符串 $$$s_i$$$。如果可以删除单元格 $$$(i, j)$$$,则 $$$s_i$$$ 的第 $$$j$$$ 个字符为 1,否则为 0。

保证所有测试用例的$$$n^2$$$总和不超过$$$10^6$$$。

输出

对于每个测试用例,如果无法精确删除 $$$(n-k+1)^2$$$ 单元格以满足条件,则输出“NO”(不带引号)。

否则,输出“YES”(不带引号)。然后,输出 $$$n$$$ 行。第 $$$i$$$ 行应包含长度为 $$$n$$$ 的二进制字符串 $$$t_i$$$。如果单元格 $$$(i, j)$$$ 被删除,则 $$$t_i$$$ 的第 $$$j$$$ 个字符为 0,否则为 1。

如果有多个解,则可以输出任意一个。

在任何情况下都可以输出“YES”和“NO”(例如,字符串“yEs”、“yes”和“Yes”将被识别为肯定响应)。

示例

输入 #1

4
2 2
10
01
4 3
1110
0101
1010
0111
5 5
01111
10111
11011
11101
11110
5 2
10000
01111
01111
01111
01111

输出 #1

YES
01
11
YES
0011
1111
1111
1100
NO
YES
01111
11000
10000
10000
10000

注意

对于第一个测试用例,您只需删除单元格 $$$(1, 1)$$$。

对于第二个测试用例,您可以选择删除单元格 $$$(1,1)$$$、$$$(1,2)$$$、$$$(4,3)$$$ 和 $$$(4,4)$$$。

对于第三个测试用例,它不是解决方案,因为对角线中的单元格将始终形成长度 $$$5$$$ 的严格递增序列。