Anti-Increasing Addicts

题意翻译

有 $n\times n$ 的方格，给定每个方格可否被删除。 给定整数 $k$ ，要求删除 $(n-k+1)^2$ 个方格，使得不存在 $k$ 个严格单调递增（横纵坐标均严格单调递增）的方格未被删除或证明其无解。 输入第一行一个整数 $t$ ，表示测试数据组数。 以下每组第一行两个整数 $n,k$ 满足 $2\le n, k\le 1000$ ，以下 $n$ 行，每行 $n$ 个数字， $1$ 表示可删除该方格， $0$ 反之。 保证所有数据中 $n^2$ 的和不超过 $10^6$ 。 对于每组测试数据，若有解，输出 $YES$ 并输出 $n$ 行，每行 $n$ 个数字， $0$ 表示该方格被删除， $1$ 反之。仅需输出任一个解。若无解输出 $NO$ 。不考虑大小写。 对于第一组数据，只能删除 $(1,1)$ 。对于第二组数据，可以删除 $(1,1),(1, 2),(4, 3),(4,4)$。对于第三组数据，没有解。

题目描述

You are given an $ n \times n $ grid. We write $ (i, j) $ to denote the cell in the $ i $ -th row and $ j $ -th column. For each cell, you are told whether yon can delete it or not. Given an integer $ k $ , you are asked to delete exactly $ (n-k+1)^2 $ cells from the grid such that the following condition holds. - You cannot find $ k $ not deleted cells $ (x_1, y_1), (x_2, y_2), \dots, (x_k, y_k) $ that are strictly increasing, i.e., $ x_i < x_{i+1} $ and $ y_i < y_{i+1} $ for all $ 1 \leq i < k $ . Your task is to find a solution, or report that it is impossible.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^5 $ ) — the number of test cases. The following lines contain the description of each test case. The first line of each test case contains two integers $ n $ and $ k $ ( $ 2 \leq k \leq n \leq 1000 $ ). Then $ n $ lines follow. The $ i $ -th line contains a binary string $ s_i $ of length $ n $ . The $ j $ -th character of $ s_i $ is 1 if you can delete cell $ (i, j) $ , and 0 otherwise. It's guaranteed that the sum of $ n^2 $ over all test cases does not exceed $ 10^6 $ .

输出格式

For each test case, if there is no way to delete exactly $ (n-k+1)^2 $ cells to meet the condition, output "NO" (without quotes). Otherwise, output "YES" (without quotes). Then, output $ n $ lines. The $ i $ -th line should contain a binary string $ t_i $ of length $ n $ . The $ j $ -th character of $ t_i $ is 0 if cell $ (i, j) $ is deleted, and 1 otherwise. If there are multiple solutions, you can output any of them. You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).

输入输出样例

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

说明

For the first test case, you only have to delete cell $ (1, 1) $ . For the second test case, you could choose to delete cells $ (1,1) $ , $ (1,2) $ , $ (4,3) $ and $ (4,4) $ . For the third test case, it is no solution because the cells in the diagonal will always form a strictly increasing sequence of length $ 5 $ .

**题目大意：**

题目要求在一个给定的 $ n \times n $ 的网格中，每个格子都有一个标记表示是否可以删除。现在给定一个整数 $ k $，需要删除恰好 $ (n-k+1)^2 $ 个格子，使得不存在 $ k $ 个严格单调递增（横纵坐标都严格单调递增）的格子未被删除，或者证明无解。

**输入输出数据格式：**

- **输入格式：**
- 第一行包含一个整数 $ t $，表示测试数据的组数。
- 每组测试数据的第一行包含两个整数 $ n, k $，满足 $ 2 \leq k \leq n \leq 1000 $。
- 接下来的 $ n $ 行，每行包含一个长度为 $ n $ 的二进制字符串，字符串中的第 $ j $ 个字符为 '1' 表示可以删除该格子，为 '0' 则相反。
- 保证所有测试数据中 $ n^2 $ 的和不超过 $ 10^6 $。

- **输出格式：**
- 对于每组测试数据，如果不存在一种删除恰好 $ (n-k+1)^2 $ 个格子的方式来满足条件，则输出 "NO"（不包含引号）。
- 否则，输出 "YES"（不包含引号），然后输出 $ n $ 行，每行一个长度为 $ n $ 的二进制字符串，表示删除后的网格状态，其中 '0' 表示该格子被删除，'1' 表示未被删除。
- 如果存在多个解，可以输出任意一个。
- "YES" 和 "NO" 的输出大小写不敏感。**题目大意：** 题目要求在一个给定的 $ n \times n $ 的网格中，每个格子都有一个标记表示是否可以删除。现在给定一个整数 $ k $，需要删除恰好 $ (n-k+1)^2 $ 个格子，使得不存在 $ k $ 个严格单调递增（横纵坐标都严格单调递增）的格子未被删除，或者证明无解。 **输入输出数据格式：** - **输入格式：** - 第一行包含一个整数 $ t $，表示测试数据的组数。 - 每组测试数据的第一行包含两个整数 $ n, k $，满足 $ 2 \leq k \leq n \leq 1000 $。 - 接下来的 $ n $ 行，每行包含一个长度为 $ n $ 的二进制字符串，字符串中的第 $ j $ 个字符为 '1' 表示可以删除该格子，为 '0' 则相反。 - 保证所有测试数据中 $ n^2 $ 的和不超过 $ 10^6 $。 - **输出格式：** - 对于每组测试数据，如果不存在一种删除恰好 $ (n-k+1)^2 $ 个格子的方式来满足条件，则输出 "NO"（不包含引号）。 - 否则，输出 "YES"（不包含引号），然后输出 $ n $ 行，每行一个长度为 $ n $ 的二进制字符串，表示删除后的网格状态，其中 '0' 表示该格子被删除，'1' 表示未被删除。 - 如果存在多个解，可以输出任意一个。 - "YES" 和 "NO" 的输出大小写不敏感。