参考程序（二维前缀和）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    // 输入网格图
    vector<vector<int>> grid(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        string row;
        cin >> row;  // 读取每一行字符串
        for (int j = 0; j < m; j++) {
            grid[i][j] = row[j] - '0';  // 将字符 '0' 或 '1' 转换为整数 0 或 1
        }
    }

    // 构建二维前缀和数组
    vector<vector<int>> prefix(n + 1, vector<int>(m + 1, 0));

    // 计算二维前缀和
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            prefix[i][j] = grid[i - 1][j - 1] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];
        }
    }

    // 最小矩形的面积初始化为一个很大的数
    int minArea = n * m + 1;

    // 枚举所有矩形的左上角和右下角
    for (int r1 = 0; r1 < n; r1++) {
        for (int r2 = r1; r2 < n; r2++) {
            for (int c1 = 0; c1 < m; c1++) {
                for (int c2 = c1; c2 < m; c2++) {
                    // 计算当前矩形内的黑色格子数量
                    int blackCount = prefix[r2 + 1][c2 + 1] - prefix[r1][c2 + 1] - prefix[r2 + 1][c1] + prefix[r1][c1];

                    // 如果黑色格子数量达到或超过K，更新最小矩形面积
                    if (blackCount >= k) {
                        minArea = min(minArea, (r2 - r1 + 1) * (c2 - c1 + 1));
                    }
                }
            }
        }
    }

    // 如果找不到至少包含K个黑色格子的矩形，输出0
    if (minArea == n * m + 1) {
        cout << 0 << endl;
    } else {
        cout << minArea << endl;
    }

    return 0;
}

参考程序（滑动窗口）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    // 输入网格图
    vector<vector<int>> grid(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        string row;
        cin >> row;
        for (int j = 0; j < m; j++) {
            grid[i][j] = row[j] - '0';  // 转换为0或1
        }
    }

    // 最小矩形面积初始化为一个很大的数
    int minArea = n * m + 1;

    // 枚举所有的列区间 [left, right]
    for (int left = 0; left < m; left++) {
        vector<int> rowSum(n, 0);  // rowSum[i]表示第i行在区间[left, right]内的黑色格子数

        for (int right = left; right < m; right++) {
            // 更新每一行的黑色格子数量
            for (int i = 0; i < n; i++) {
                rowSum[i] += grid[i][right];
            }

            // 使用滑动窗口来计算至少包含K个黑色格子的最小矩形的高度
            int blackCount = 0;  // 当前滑动窗口中的黑色格子数量
            int top = 0;         // 滑动窗口的上边界
            for (int bottom = 0; bottom < n; bottom++) {
                blackCount += rowSum[bottom];

                // 当窗口中的黑色格子数达到或超过K时，更新最小矩形面积
                while (blackCount >= k) {
                    minArea = min(minArea, (right - left + 1) * (bottom - top + 1));
                    blackCount -= rowSum[top++];
                }
            }
        }
    }

    // 如果没有找到符合条件的矩形，输出0
    if (minArea == n * m + 1) {
        cout << 0 << endl;
    } else {
        cout << minArea << endl;
    }

    return 0;
}