309807: CF1738G. Anti-Increasing Addicts

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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 $ .

Input

题意翻译

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

Output

**题目大意:**

题目要求在一个给定的 $ 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" 的输出大小写不敏感。

加入题单

上一题 下一题 算法标签: