gesp(C++五级)（9）洛谷：B10719：[GESP202406 五级] 黑白格

gesp(C++五级)（9）洛谷：B10719：[GESP202406 五级] 黑白格

题目描述

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

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

输入格式

第一行包含三个正整数 $n,m,k$，含义如题面所示。

之后 $n$ 行，每行⼀个长度为 $m$ 的 $\text{01}$ 串，代表网格图第 $i$ 行格子的颜色，如果为 $\text{0}$，则对应格子为白色，否则为黑色。

输出格式

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

样例 #1

样例输入 #1

4 5 5
00000
01111
00011
00011

样例输出 #1

6

提示

样例解释

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

数据范围

对于全部数据，保证有 $1\le n,m\le 100$，$1\le k\le n\times m$。

子任务编号	得分	$n,m$
$1$	$20$	$\le 10$
$2$	$40$	$n=1$，$1\le m\le 100$
$3$	$40$	$\le 100$

Update on 2024/7/9：添加了若干组 hack 数据，感谢 @cff_0102 的贡献。

AC代码（100分）

#include<bits/stdc++.h>
using namespace std;
/*思路2： 
   二维前缀和：
      枚举所有左上角和右下角顶点构成的子矩阵
  然后使用二维前缀和，计算其黑格出现的次数，看是否满足要求 
备注： 所有测试点满足时间复杂度的要求，得分100 
*/
int n,m,k,ans=10001;
char c;//字符变量，实现每个字符的输入
int a[110][110];//二维前缀和数组：左上角（1,1）到右下角(i,j)的子矩阵黑格的数量 

int main(){
//输入 
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>c;
if(c=='1') a[i][j]++;//黑格数量加1
a[i][j]=a[i][j]+a[i][j-1]+a[i-1][j]-a[i-1][j-1]; //构造二维前缀和 
}
}
//枚举矩阵的左上角和右下角的顶点
for(int i1=1;i1<=n;i1++){//左上角 
for(int j1=1;j1<=m;j1++){
for(int i2=i1;i2<=n;i2++){//右下角 
for(int j2=j1;j2<=m;j2++){
//使用二维前缀和计算子矩阵中黑格的数量
int cnt=a[i2][j2]-a[i2][j1-1]-a[i1-1][j2]+a[i1-1][j1-1]; 
//判断黑格数量是否大于等于k
if(cnt>=k){
int sum=(i2-i1+1)*(j2-j1+1);//计算子矩阵的格子数
ans=min(ans,sum); 
}
}
}
}
} 
//输出
if(ans==10001) cout<<0;
else cout<<ans; 
return 0;
}

文末彩蛋：

点击王老师青少年编程主页有更多精彩内容

原文地址：https://blog.csdn.net/weixin_66461496/article/details/145229377

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！