B4005 [GESP202406 四级] 黑白方块 【暴力枚举】【前缀和】

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,tmp;
char mp[20][20];
int cheak(int a,int b,int c,int d){
//a<=c  b<=d
int cnt=0;
//枚举矩阵中的每个点 
for(int i=a;i<=c;i++)
for(int j=b;j<=d;j++)
if(mp[i][j]=='1') cnt++;//统计黑格的个数 

return 2*cnt==(c-a+1)*(d-b+1);//如果黑格子的数量为总数的一半，则为平衡矩阵 
}

int main(){
cin>>n>>m;
//输入二维矩阵没有空格，一定要用char[][] 
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>mp[i][j];
//不降原则枚举矩形的左上角（i,j）和右下角 (ii,jj)
for (int i = 1; i <= n; i++) { 
for (int j = 1; j <= m; j++) {
for (int ii = i; ii <= n; ii++) {
for (int jj = j; jj <= m; jj++) {
if (cheak(i, j, ii, jj)){//cheak检查当前矩阵是否是平衡矩阵 
//利用 (ii - i + 1) * (jj - j + 1)求出矩阵中点的总数 
ans = max(ans, (ii - i + 1) * (jj - j + 1));
}

}
}
}
}
cout << ans << endl;
return 0;
}

 以上为暴力枚举，以下为二维前缀和

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,tmp,sum[20][20];
char mp[20][20];
int cheak(int a,int b,int c,int d){
//a<=c  b<=d  
//利用前缀和获得区间和（黑格子的数量） 
int cnt=sum[c][d]-sum[a-1][d]-sum[c][b-1]+sum[a-1][b-1];
return 2*cnt==(c-a+1)*(d-b+1);//如果黑格子的数量为总数的一半，则为平衡矩阵 
}

int main(){
cin>>n>>m;
//输入二维矩阵没有空格，一定要用char[][] 
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>mp[i][j];
//求黑格子前缀和 
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(mp[i][j]=='1') 
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+1;
else 
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+0;
}

//不降原则枚举矩形的左上角（i,j）和右下角 (ii,jj)
for (int i = 1; i <= n; i++) { 
for (int j = 1; j <= m; j++) {
for (int ii = i; ii <= n; ii++) {
for (int jj = j; jj <= m; jj++) {
if (cheak(i, j, ii, jj)){//cheak检查当前矩阵是否是平衡矩阵 
//利用 (ii - i + 1) * (jj - j + 1)求出矩阵中点的总数 
ans = max(ans, (ii - i + 1) * (jj - j + 1));
}

}
}
}
}
cout << ans << endl;
return 0;
}

原文地址：https://blog.csdn.net/hls0611/article/details/140698409

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