题解 | #最小面积子矩阵# 前缀和矩阵

#include <iostream>
using namespace std;
#define MAX 101
#define INF 0x7fffffff
int sumOfMat(int i, int j, int width, int length, int(&arr)[MAX][MAX]){
// 统计从(i,j)为首的矩阵的所有元素和
    int sum;
    sum=arr[i+width-1][j+length-1]-arr[i-1][j+length-1]-arr[i+width-1][j-1]+arr[i-1][j-1];
    return sum;
}
int minMatArea(int n, int m, int k, int(&arr)[MAX][MAX]) { // 使用引用传递二维数组
    int minArea = INF; 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for(int width=1;width<=n-i+1;width++){ // 特别注意 width、length上界
                for(int length=1;length<=m-j+1;length++){
                    int curSum=sumOfMat(i, j, width, length, arr);                 
                    if(curSum>=k && minArea>=width*length){
                        // 更新条件：1、sum >= k 2、area最小
                        minArea=width*length;
                    }
                }
            }
        }
    }
    if(minArea==INF) minArea=-1;
    return minArea;
}
int main() {
    int arr[MAX][MAX]={0}; // 首行列全部初始化为0
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) { // 读取数据，并计算前缀和矩阵
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
            arr[i][j]+=arr[i-1][j]+arr[i][j-1]-arr[i-1][j-1];
        }
    }
    cout << minMatArea(n, m, k, arr) << endl;
    return 0;
}