返回首页 返回题库

黑白格

C++ 中等 GESP五级真题 #双指针#二分查找

题目描述

题面描述

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

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

输入格式

第一行包含三个正整数 ,含义如题面所示。

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

输出格式

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

样例1

输入:

4 5 5
00000
01111
00011
00011

输出:

6

样例解释

对于样例1,假设 代表第 行第 列,至少包含5个黑色格子的最小子矩形的四个顶点为 ,共包含6个格子。

样例2

输入:

2 2 2
10
01

输出:

4

数据范围

对于全部数据,保证有 。

时间限制

1.0 s

内存限制

512.0 MB

💡 查看提示(先自己想一想再看)
本题考察前缀和与枚举优化,可通过固定左右列边界,将二维问题转化为一维的连续子数组和问题,再结合前缀和与二分查找或滑动窗口快速求解满足和大于等于k的最短子数组长度,从而得到最小矩形面积。
⚙ 开始做这道题 0 人做过 · 0 收藏 · 3 浏览

讨论(0)