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\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)$。对于第三组数据，没有解。