1 条题解
-
0
#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
- 上传者