二维前缀和优化版本

题目分析

给定一个 $n \times m$ 的 01 网格，要求找出一个最大的子矩形，使得其中 0 和 1 的数量相等。输出这个子矩形的面积（格子数），如果不存在则输出 0。

---

核心思路

关键转化：把 0 变成 -1

题目要求"0 和 1 数量相同"，如果我们把：

• 1 记为 +1
• 0 记为 -1

那么一个矩形中 0 和 1 数量相同 $\iff$ 矩形内所有数的和等于 0。

这样问题就转化为：求元素和等于 0 的最大子矩形面积。

二维前缀和

设 sum[i][j] 表示从 (1,1) 到 (i,j) 这个矩形的元素和，则：

$$sum[i][j] = sum[i-1][j] + sum[i][j-1] + t - sum[i-1][j-1]$$

其中 t 是 (i,j) 处的值（1 或 -1）。

那么任意子矩形 (i1, j1) 到 (i, j)（左上角到右下角）的元素和为：

$$S = sum[i][j] - sum[i][j_1-1] - sum[i_1-1][j] + sum[i_1-1][j_1-1]$$

暴力枚举

由于数据范围较小（网格尺寸不大），我们可以直接枚举所有子矩形：

• 枚举右下角 (i, j)
• 枚举左上角 (i1, j1)
• 用前缀和 $O(1)$ 算出该子矩形的和
• 若和为 0，更新最大面积

复杂度 $O(n^2 m^2)$，对于本题的数据范围可以接受。

---

代码详解

#include<bits/stdc++.h>
using namespace std;
using ll = long long int;

char a[20][20];      // 存储原始网格（01字符）
int sum[20][20];     // 二维前缀和

void solve()
{
    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 t = a[i][j] - '0';   // 字符转数字
            if(t == 0) t = -1;       // 关键转化：0 变 -1
            // 二维前缀和递推
            sum[i][j] = sum[i-1][j] + sum[i][j-1] + t - sum[i-1][j-1];
        }
    }

    int maxx = 0;   // 注意初始化 0（不存在时输出 0）

    // 枚举右下角 (i, j)
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            // 枚举左上角 (i1, j1)
            for(int i1 = 1; i1 <= i; i1++)
            {
                for(int j1 = 1; j1 <= j; j1++)
                {
                    // 计算子矩形和
                    int ans = sum[i][j] - sum[i][j1-1] 
                            - sum[i1-1][j] + sum[i1-1][j1-1];
                    
                    if(ans == 0)   // 和 == 0
                    {
                        int t = (i - i1 + 1) * (j - j1 + 1);  // 面积
                        maxx = max(maxx, t);
                    }
                }
            }
        }
    }

    cout << maxx << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}

算法复杂度

• 时间：$O(n^2 m^2)$，四重循环枚举
• 空间：$O(nm)$，存储前缀和