C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int M,N,K,MIN=0x7fffffff;
int a[110][110];
int dp[110][110];//存储(i,j)元素左上角矩阵的全部和，方便以O（1）的复杂度获取任意矩阵的和，类似于前缀和思维

int sumd(int i,int j ,int m ,int n){//以 ij为起点，长宽分别为m，n的矩阵大小
    return dp[i+m-1][j+n-1] - dp[i+m-1][j-1] - dp[i-1][j+n-1] + dp[i-1][j-1];
}

int main()
{
    int sum = 0;
    cin>>N>>M>>K;
    for(int i =1;i<=N;i++){
        for(int j =1;j<=M;j++){
            cin >> a[i][j];
        }
    }
    for(int j = 1;j<=M;j++){
        for(int i =1;i<=N;i++){
            dp[i][j] =a[i][j]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];//左上角矩阵和数组
        }
    }

    if(dp[N][M]<K){
        cout << -1;
        return 0;
    }
    int i,j;
    for(int n = 1;n<=N;n++){
        for(int m = 1;m<=M;m++){//枚举矩阵大小
            i = 1;j=1;
            for(int i = 1;i+n-1<=N;i++){
                for(int j =1;j+m-1<=M;j++){
                    if(sumd(i,j,n,m)>=K){
                        if(m*n<MIN){
                            MIN = m*n;
                        }
                        i=N;//如果当前m*n大小找到了一个不小于K的剩下的就不需要枚举了直接跳出ij的循环
                        j=M;
                    }
                }
            }
        }
    }
    cout << MIN;
}