【蓝桥杯】剪格子-CSDN博客

　　本题目链接：https://www.lanqiao.cn/courses/2784/exams/3864/question_sets/16435/problems/WB1/

　　题目描述

　　现在有一个二维码，我们要把它裁剪成一个 n 行 m 列的小二维码。当然，裁剪时我们可以只截取一个小于 n 行 m 列的区域，但是这个区域必须包含原来的二维码。

　　现在，我们已经知道了原来的二维码的大小，以及每一个格子的黑白情况，问：是否存在一种裁剪方案，能够得到一个小二维码，使得这个小二维码恰好包含 k 个黑色格子？

　　请注意，这个二维码是以字符串形式给出的。其中，字符串中的 “1” 表示黑色格子，字符串中的 “0” 表示白色格子。字符串中的回车和空格都需要忽略。

　　输入格式

　　输入的第一行包含三个整数 n, m 和 k，分别表示原始二维码的行数、列数，以及小二维码中要求包含的黑色格子数。

　　输入的第二行到第 n + 1 行，每行包含一个长度为 m 的字符串，表示原始二维码。

　　输出格式

　　如果存在一种裁剪方案，能够得到一个小二维码，使得这个小二维码恰好包含 k 个黑色格子，则输出 Yes，否则输出 No。

　　样例输入1

　　5 5 2

　　00000

　　00100

　　01110

　　00100

　　00000

　　样例输出1

　　Yes

　　样例输入2

　　5 5 2

　　00000

　　00100

　　01110

　　00110

　　00000

　　样例输出2

　　No

　　数据规模与约定

　　对于 30% 的数据，1 <= n, m <= 10，1 <= k <= 5。

　　对于 60% 的数据，1 <= n, m <= 50，1 <= k <= 25。

　　对于 100% 的数据，1 <= n, m <= 100，1 <= k <= n * m。

　　时间限制：1s

　　空间限制：256MB

　　思路分析

　　本题目可以采用暴力枚举的方法来解决，我们可以先得到原先二维码中的黑色格子数目，然后再枚举所有的情况，看看是否有一种情况满足条件即可。

　　具体步骤如下：

　　首先，我们需要先统计一下原先二维码中的黑色格子数目，这个可以用一个计数器来实现，每当一个格子为黑色时，计数器加一即可。

　　接着，我们枚举裁剪后的小二维码的左上角位置，即枚举左上角是第 i 行第 j 列的方格，可以用两层循环来实现。

　　然后，我们再在这个位置上枚举所有可能的小二维码大小，即从这个位置开始向右最多可以扩展的列数为 min(m-j+1, k)，向下最多可以扩展的行数为 min(n-i+1, k)，从最小的大小开始，逐渐增大。

　　在每个大小下，我们可以统计一下小二维码中黑色格子的数目，如果恰好等于 k，那么就说明满足条件，输出 Yes，结束程序。如果一直到最大的大小都没有满足条件，那么就说明不存在这样的方案，输出 No 即可。

　　代码实现