CF1738G Anti-Increasing Addicts

给定一个 $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)$，使得它们严格递增，即对于所有 $1 \leq i < k$，都有 $x_i < x_{i+1}$ 且 $y_i < y_{i+1}$。 你的任务是找到一种满足条件的删除方案，或者报告无解。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 10^5$）——表示测试用例的数量。接下来的每组测试数据描述如下。 每组测试数据的第一行包含两个整数 $n$ 和 $k$（$2 \leq k \leq n \leq 1000$）。 接下来有 $n$ 行，每行包含一个长度为 $n$ 的二进制字符串 $s_i$。如果 $s_i$ 的第 $j$ 个字符为 1，表示可以删除 $(i, j)$ 这个格子，否则不能删除。 保证所有测试用例中 $n^2$ 的总和不超过 $10^6$。

对于每组测试数据，如果不存在恰好删除 $(n-k+1)^2$ 个格子的方案满足条件，输出 "NO"（不带引号）。 否则，输出 "YES"（不带引号）。然后输出 $n$ 行，每行一个长度为 $n$ 的二进制字符串 $t_i$。如果 $(i, j)$ 这个格子被删除，则 $t_i$ 的第 $j$ 个字符为 0，否则为 1。 如果有多种方案，输出任意一种均可。 你可以用任意大小写输出 "YES" 和 "NO"（例如 "yEs"、"yes"、"Yes" 都会被识别为肯定回答）。

对于第一个测试用例，你只需要删除 $(1, 1)$ 这个格子。 对于第二个测试用例，你可以选择删除 $(1,1)$、$(1,2)$、$(4,3)$ 和 $(4,4)$ 这四个格子。 对于第三个测试用例，无解，因为对角线上的格子总能组成长度为 $5$ 的严格递增序列。 由 ChatGPT 4.1 翻译