二维前缀和+滑动窗口优化

这个题目数据范围是$n,m \leq100$，就算先进行二维前缀和优化，然后枚举左上角和右下角坐标，时间复杂度为$O(n^4)$，极有可能超时，但是实际上可以通过，就需要进行优化

步骤 1：前缀和预处理（二维转一维辅助）

首先计算矩阵的二维前缀和，目的是快速计算任意子矩形的元素和。
前缀和数组 $a[i][j]$ 定义：表示以 $(1,1)$ 为左上角、$(i,j)$为右下角的子矩形的元素和（注意：代码中直接在原矩阵上修改存储前缀和，空间优化）。
前缀和公式：$a[i][j] = 原a[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1]$（容斥原理，避免重复计算）。
前缀和在这里不进行赘述

for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            a[i][j] = a[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1]; // 前缀和

步骤 2：枚举行范围（压缩维度 $O(n^2)$）

枚举所有可能的 “上下行边界” 组合 $(i,j)（i 为上行，j 为下行，1≤i≤j≤n）$：
对于每个固定的行范围 $[i,j]$，问题转化为：在这 $j-i+1$ 行中，找到一个列范围 $(l,r]$，使得该列范围内的元素和 $≥k$，且矩形面积 $(j-i+1)*(r-l)$ 最小。

从第 $i$ 行到第 $j$ 行，第 $l+1$ 列到第第 $r$ 列 的面积就是 $(j-i+1)*(r-l)$

步骤 3：滑动窗口找最小列范围（一维优化 $O(m)$）

for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j++) // 枚举从第i行到第j行
        {
            int l = 0, sum = 0;          // l:左边界，sum:从第i行到第j行的第1列的和
            for (int r = 1; r <= m; r++) // 枚举右边界
            {
                sum = a[j][r] - a[j][l] - a[i - 1][r] + a[i - 1][l]; // 当前矩形的和
                int tmp = (j - i + 1) * (r - l);                     // 当前矩形的面积
                if (sum >= k)
                    ans = min(ans, tmp); // 更新最小面积
                while (a[j][r] - a[j][l + 1] - a[i - 1][r] + a[i - 1][l + 1] >= k)
                {
                    sum = a[j][r] - a[j][l + 1] - a[i - 1][r] + a[i - 1][l + 1]; // 更新当前矩形的和
                    l++;                                                         // 左边界右移
                    ans = min(ans, (j - i + 1) * (r - l));                       // 更新最小面积
                }
            }
        }
    }

对于固定的行范围 $[i,j]$，用双指针（滑动窗口） 遍历列：
右指针 $r$ 从 $1$ 到 $m$ 逐步扩展（扩大窗口右边界）。
左指针 $l$ 初始为 $0$ (不包含第 $l$ 列的数据 )，当窗口内的和 $≥k$ 时，尝试右移 $l$ 缩小窗口，直到和 $<k$，期间不断更新最小面积。
窗口和计算：利用前缀和快速得到 $[i,j]$ 行、$[l+1,r]$ 列的子矩形和：$sum = a[j][r] - a[j][l] - a[i-1][r] + a[i-1][l]$。

最终代码(时间复杂度$O(n^2m)$)

#include <bits/stdc++.h>
#define N 105

using namespace std;

int n, m, ans = 100 * 100, k;
int a[N][N];

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%1d", &a[i][j]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            a[i][j] = a[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1]; // 前缀和

    if (a[n][m] < k) // 特判
    {
        printf("0");
        return 0;
    }
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++) // 枚举从第i行到第j行
        {
            int l = 0, sum = 0;          // l:左边界，sum:从第i行到第j行的第1列的和
            for (int r = 1; r <= m; r++) // 枚举右边界
            {
                sum = a[j][r] - a[j][l] - a[i - 1][r] + a[i - 1][l]; // 当前矩形的和
                int tmp = (j - i + 1) * (r - l);                     // 当前矩形的面积
                if (sum >= k)
                    ans = min(ans, tmp); // 更新最小面积
                while (a[j][r] - a[j][l + 1] - a[i - 1][r] + a[i - 1][l + 1] >= k)
                {
                    sum = a[j][r] - a[j][l + 1] - a[i - 1][r] + a[i - 1][l + 1]; // 更新当前矩形的和
                    l++;                                                         // 左边界右移
                    ans = min(ans, (j - i + 1) * (r - l));                       // 更新最小面积
                }
            }
        }
    printf("%d", ans);
    return 0;
}