⿊⽩格

题目描述

⼩杨有⼀个 ⾏ 列的⽹格图，其中每个格⼦要么是⽩⾊，要么是⿊⾊。 ⼩杨想知道⾄少包含 个⿊⾊格⼦的最⼩⼦矩形包含了多少个格⼦。

输入格式

第⼀⾏包含三个正整数 ，含义如题⾯所⽰。 之后 ⾏，每⾏⼀个长度为 的 串，代表⽹格图第 ⾏格⼦的颜⾊，如果为 ，则对应格⼦为⽩⾊，否则为⿊ ⾊。

输出格式

输出⼀个整数，代表⾄少包含 个⿊⾊格⼦的最⼩⼦矩形包含格⼦的数量，如果不存在则输出 。 3.1.4 样例1 1 4 5 5 2 00000 3 01111 4 00011 5 00011 1 6 3.1.5 样例解释 对于样例1，假设 ( ) 代表第 ⾏第 列，⾄少包含 个⿊⾊格⼦的最⼩⼦矩形的四个顶点为 ( )，( )，( )，( )，共包含 个格⼦。 3.1.6 数据范围 子任务编号 数据点占比 1 20% 2 40% 3 40% 对于全部数据，保证有 。 3.1.7 参考程序 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 110; 4 int w[N][N]; 5 int sum[N][N]; 6 int n,m; 7 8 int main(){ 9 int k; 10 cin>>n>>m>>k; 11 for(int i=1;i<=n;i++){ 12 string s; 13 cin>>s; 14 for(int j=1;j<=m;j++){ 15 w[i][j]=s[j-1]-'0'; 16 sum[i][j]=sum[i][j-1]+w[i][j]; 17 } 18 } 19 int ans = 0; 20 for(int i=1;i<=m;i++){ 21 for(int j=i;j<=m;j++){ 22 vector num; 23 int now = 0; 24 for(int l=1;l<=n;l++){ 25 int tmp = sum[l][j]-sum[l][i-1]; 26 now+=tmp; 27 num.push_back(now); 28 if(now>=k){ 29 if(ans ==0)ans=(j-i+1)l; 30 else ans=min(ans,(j-i+1)l); 31 int L=1,R=l; 32 while (L < R){ 33 int mid = L + R + 1 >> 1; 34 if (now-num[mid-1]>=k) L = mid; 35 else R = mid - 1; 36 } 37 if(now-num[L-1]>=k){ 38 if(ans ==0)ans=(j-i+1)(l-L); 39 else ans=min(ans,(j-i+1)(l-L)); 40 } 41 } 42 } 43 } 44 } 45 cout<<ans<<"\n"; 46 }

样例输入 #1

1 4 5 5
2 00000
3 01111
4 00011
5 00011
1 6

样例输出 #1

样例解释 #1

对于样例1，假设 ( ) 代表第 ⾏第 列，⾄少包含 个⿊⾊格⼦的最⼩⼦矩形的四个顶点为 ( )，( )，( )，( )，共包含 个格⼦。

数据范围

子任务编号 数据点占比 1 20% 2 40% 3 40% 对于全部数据，保证有 。

知识点与难度

本题涉及的知识点从属于 GESP 5级，难度等级：⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。