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<=dint 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;
}