gesp(C++四级)（11）洛谷：B4005：[GESP202406 四级] 黑白方块

在这里插入图片描述

题目描述

小杨有一个 $n$ 行 $m$ 列的网格图，其中每个格子要么是白色，要么是黑色。对于网格图中的一个子矩形，小杨认为它是平衡的当且仅当其中黑色格子与白色格子数量相同。小杨想知道最大的平衡子矩形包含了多少个格子。

输入格式

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

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

输出格式

输出一个整数，代表最大的平衡子矩形包含格子的数量，如果不存在则输出 $0$ 。

样例 #1

样例输入 #1

样例输出 #1

提示

【样例解释】

对于样例 $1$ ，假设 $(i, j)$ 代表第 $i$ 行第 $j$ 列，最大的平衡子矩形的四个顶点分别为 $(1, 2), (1, 5), (4, 2), (4, 5)$ 。

【数据范围】

对于全部数据，保证有 $1\leq n,m\leq 10$ 。

AC代码（100分）

#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0; 
char a[20][20];
//函数：判断是否是平衡矩形 
bool check(int i1,int j1,int i2,int j2){
	int n0=0,n1=0;//统计0和1的数量
	for(int i=i1;i<=i2;i++){
		for(int j=j1;j<=j2;j++){
			if(a[i][j]=='0') n0++;
			else n1++;
		}
	} 
	if(n0==n1) return true;//如果0和1的数量相等，返回true 
	else return false;//否则，返回false 
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	//枚举所有可能的左上角到右下角的子矩形 
	for(int i1=1;i1<=n;i1++){//枚举左上角的顶点(i1,j1)
		for(int j1=1;j1<=m;j1++){
			for(int i2=i1;i2<=n;i2++){//枚举右下角的顶点(i2,j2) 
				for(int j2=j1;j2<=m;j2++){
					if(check(i1,j1,i2,j2)){
						ans=max(ans,(i2-i1+1)*(j2-j1+1));
					}
				}
			} 
		}
	}
	cout<<ans; 
	return 0;
}