1 条题解

  • 0
    @ 2026-1-28 12:59:46
    #include<iostream>
    using namespace std;
    
    // [1] arr数组-存储原始的01网格(0=白色,1=黑色),最多支持20×20的网格
    int arr[20][20];
    // [2] brr数组-前缀和数组,用于快速计算任意子矩形内黑色格子(1)的数量
    int brr[20][20];
    
    int main(){
        // [3] n-网格的行数;m-网格的列数
    	int n,m;
        cin>>n>>m;
        // [4] 读取n行01字符串,转换为整数存入arr数组
    	for(int i=0;i<n;i++){
    		string s;
    		cin>>s;
    		for(int j=0;j<m;j++){
    			arr[i][j]=s[j]-'0';  // 字符转整数('0'→0,'1'→1)
    		}
    	}
    	
        // [5] 构建前缀和数组brr
    	for(int i=0;i<n;i++){
    		for(int j=0;j<m;j++){
    			brr[i][j]=arr[i][j];  // 初始值为当前格子的颜色(1或0)
    			if(i-1>=0)	brr[i][j]+=brr[i-1][j];  // 加上方格子的前缀和(如果存在)
    			if(j-1>=0)	brr[i][j]+=brr[i][j-1];  // 加左方格子的前缀和(如果存在)
    			if(j-1>=0 && i-1 >=0 )	brr[i][j]-=brr[i-1][j-1];  // 减去左上方格子的前缀和(避免重复计算)
    		}
    	}
    	
        // [6] max_num-最大平衡矩形的面积;flag-标记是否存在平衡矩形(1=存在,0=不存在)
    	int max_num=0,flag=0;
        // [7] 枚举所有可能的子矩形:(i,j)为左上角坐标,(k,l)为右下角坐标
    	for(int i=0;i<n;i++){  // 左上角行号
    		for(int j=0;j<m;j++){  // 左上角列号
    			for(int k=i;k<n;k++){  // 右下角行号(≥左上角行号)
    				for(int l=j;l<m;l++){  // 右下角列号(≥左上角列号)
                        // [8] 计算子矩形(i,j)-(k,l)内黑色格子的数量(前缀和公式)
    					int sum=brr[k][l];
    					if(i-1>=0) sum-=brr[i-1][l];  // 减去上方矩形的前缀和
    					if(j-1>=0) sum-=brr[k][j-1];  // 减去左方矩形的前缀和
    					if(j-1>=0 && i-1>=0) sum+=brr[i-1][j-1];  // 加上左上方矩形的前缀和(因重复减了两次)
                        
                        // [9] 计算子矩形的面积
    					int mj=(k-i+1)*(l-j+1);
                        // [10] 判断是否为平衡矩形:黑色格子数=白色格子数 → sum*2 == 面积(因为面积=黑+白,黑=白则黑=面积/2)
    					if(sum*2 == mj){
    						flag=1;
    						max_num=max(max_num ,mj);  // 更新最大面积
    					}
    				} 
    			}
    		} 
    	}
        // [11] 输出结果:存在平衡矩形则输出最大面积,否则输出0
    	if(flag==1) cout<<max_num;
    	else cout<<0;
    	return 0;
    }
    
    • 1

    信息

    ID
    900
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    2
    已通过
    2
    上传者