蓝桥杯C语言裁剪二维码

本题目链接：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 即可。

代码实现