暴力枚举

#include <iostream>
using namespace std;
char a[20][20];
int main(){
    int n , m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    int ans = 0;
    for(int i=n;i>=1;i--){
        for(int j=m;j>=1;j--){
            for(int bx = 1;bx+i-1<=n;bx++){
                for(int by=1;by+j-1<=m;by++){
                    int sum0 = 0 , sum1 = 0;
                    for(int x=bx;x<=bx+i-1;x++){
                        for(int y=by;y<=by+j-1;y++){
                            if(a[x][y]=='0') sum0++;
                            else sum1++;
                        }
                    }
                    if(sum0==sum1){
                        ans = max(ans, i*j);
                    }
                }
            }
            
            
        }
    }
    cout<<ans;
    return 0;
}

使用暴力枚举法。由于题目给出的数据范围非常小（$1 \le n, m \le 10$），直接枚举所有可能的子矩形并统计黑白格子数量是完全可行的，且逻辑非常直观。

下面为你逐层拆解代码的含义：

1. 核心思路：六重循环枚举

代码的核心是通过 6 层 for 循环，把网格中所有可能的子矩形都遍历一遍，逐一检查是否“平衡”（黑格数量 == 白格数量），并记录最大面积。

2. 逐段代码详解

读入数据

char a[20][20];
// ...
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        cin>>a[i][j];
    }
}

• 使用 char 二维数组存储网格，下标从 1 开始，方便后续计算。
• 数组开 20 是为了留出安全边界，防止越界。

② 枚举矩形的【高度】和【宽度】

for(int i=n;i>=1;i--){      // i 表示子矩形的高度
    for(int j=m;j>=1;j--){  // j 表示子矩形的宽度

• 外层两层循环确定我们要找的矩形尺寸。
• 这里从大到小枚举（i=n 到 1），虽然不能提前结束循环（因为大矩形不平衡不代表小矩形也不平衡），但符合直觉：优先检查面积大的矩形。

③ 枚举矩形的【左上角位置】

for(int bx = 1; bx+i-1<=n; bx++){  // bx 表示左上角的行号
    for(int by = 1; by+j-1<=m; by++){ // by 表示左上角的列号

• 确定了高 i 宽 j 后，矩形可以在网格内滑动。
• bx 和 by 遍历所有合法的左上角起点。条件 bx+i-1<=n 保证矩形不会超出网格下边界，by+j-1<=m 保证不超出右边界。

统计矩形内的黑白格子

int sum0 = 0, sum1 = 0;
for(int x=bx; x<=bx+i-1; x++){      // 遍历矩形覆盖的每一行
    for(int y=by; y<=by+j-1; y++){  // 遍历矩形覆盖的每一列
        if(a[x][y]=='0') sum0++;
        else sum1++;
    }
}

• 最内层两层循环进入当前确定的子矩形内部，逐个格子检查。
• '0' 代表白色，sum0 计数；'1'（或 else）代表黑色，sum1 计数。

⑤ 判断平衡并更新答案

if(sum0 == sum1){
    ans = max(ans, i * j);
}

• 如果白格和黑格数量相等，说明当前矩形是平衡的。
• i * j 就是当前矩形的面积（包含的格子总数）。用 max 函数保留历史最大值。
• ans 初始为 0，如果全程找不到平衡矩形，自然输出 0，完美符合题目“不存在则输出0”的要求。

---

📊 3. 复杂度分析（为什么不会超时？）

• 子矩形总数约为 $\frac{n(n+1)}{2} \times \frac{m(m+1)}{2} \approx O(n^2 m^2)$
• 每个子矩形统计需要 $O(i \times j) \approx O(nm)$
• 总时间复杂度：$O(n^3 m^3)$
• 当 $n=m=10$ 时，最大运算量约为 $10^6$ 次。现代计算机 1 秒可执行约 $10^8$ 次运算，因此绰绰有余。

---

4. 扩展优化

如果题目数据范围扩大到 $n, m \le 500$，暴力法会超时。此时需要引入二维前缀和优化：

1. 预处理前缀和数组 pre[i][j]，表示从 (1,1) 到 (i,j) 的矩形中 '1' 的个数。
2. 任意子矩形内 '1' 的个数可通过公式 $O(1)$ 算出：cnt1 = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1]
3. '0' 的个数 = 矩形总面积 - cnt1。
4. 优化后复杂度降至 $O(n^2 m^2)$，可轻松处理 $500 \times 500$ 的数据。