3865 - 黑白格

题目描述

小杨有一个 nnmm 列的网格图,其中每个格子要么是白色,要么是黑色。

小杨想知道至少包含 kk 个黑色格子的最小子矩形包含了多少个格子。

输入

第一行包含三个正整数 nmkn,m,k ,含义如题目所示。

之后 nn 行,每行一个长度为 mm0101 串,代表网格图第 ii 行格子的颜色,如果为 00,则对应格子为白色,否则为黑色。

输出

输出一个整数,代表至少包含 kk 个黑色格子的最小子矩形包含格子的数量,如果不存在则输出 00

样例

输入
复制

4 5 5
00000
01111
00011
00011

输出
复制

6
说明

【样例解释】

对于样例 11,假设 (ij)(i,j) 代表第 ii 行第 jj 列,至少包含 55 个黑色格子的最小子矩形的四个顶点为 (24)(25)(44)(45)(2,4),(2,5),(4,4),(4,5),共包含 66 个格子。

【数据范围】

对于全部数据,保证有 1nm100 1 \le n,m \le 100 1kn×m 1 \le k \le n \times m

来源

2024年GESP 6月认证C++五级真题

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 113
通过人数 40
金币数量 1 枚
难度 基础


上一题 下一题