A32278. 黑白方块题面描述小杨有一个n行m列的网格图，其中每个格子要么是白色，要么是黑色。对于网格图中的一个子矩形，小杨认为它是平衡的当且仅当其中黑色格子与白色格子数量相同。小杨想知道最大的平衡子矩形包含了多少个格子。
填空题
较难
知识点
题目描述
黑白方块
题面描述
小杨有一个n行m列的网格图，其中每个格子要么是白色，要么是黑色。
对于网格图中的一个子矩形，小杨认为它是平衡的当且仅当其中黑色格子与白色格子数量相同。
小杨想知道最大的平衡子矩形包含了多少个格子。
输入格式
第一行包含两个正整数n,m，含义如题面所示。
之后n行，每行一个长度为m的01串，代表网格图第i行格子的颜色，如果为0，则对应格子为白色，否则为黑色。
输出格式
输出一个整数，代表最大的平衡子矩形包含格子的数量，如果不存在则输出 0。
样例1
输入
4 5
00000
01111
00011
00011
输出
16
样例解释
对于样例1，假设 (i,j) 代表第i行第j列，最大的平衡子矩形的四个顶点分别为 (1,2)，(1,5)，(4,2)，(4,5)。
数据范围
对于全部数据，保证有 1<= n,m <=10。
参考答案
#include<bits/stdc++.h> using namespace std; const int N = 55;
int w[N][N];
int n,m;
bool check(int xa,int ya,int xb,int yb) {
int a[2]= {0,0};
for(int i = xa; i<=xb; i++) {
for(int j=ya; j<=yb; j++) {
a[w[i][j]]++;
}
}
return a[0]==a[1];
}
int main() {
cin>>n>>m;
for(int i=1; i<=n; i++) {
string s;
cin>>s;
for(int j=1; j<=m; j++) {
w[i][j]=s[j-1]-'0';
}
}
int ans = 0;
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(check(i,j,ii,jj)) {
ans = max(ans,(ii-i+1)*(jj-j+1));
}
}
}
}
}
cout<<ans<<"\n";
}
上一题
下一题