【机试】最小面积子矩阵_2. 一个n*m的矩阵,找出这个矩阵中所有元素的和不小于k的面积最小的子矩阵(矩阵中

最小面积子矩阵

来源：上海交通大学

题目描述

一个N*M的矩阵，找出这个矩阵中所有元素的和不小于K的面积最小的子矩阵（矩阵中元素个数为矩阵面积）

输入描述

每个案例第一行三个正整数N,M<=100，表示矩阵大小，和一个整数K 接下来N行，每行M个数，表示矩阵每个元素的值

输出描述:

输出最小面积的值。如果出现任意矩阵的和都小于K，直接输出-1。

输入

4 4 10
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

输出

1

#include<bits/stdc++.h>
#define MAX 0x3f3f3f3f
using namespace std;
int a[101][101];
int sum[101][101][101];//第i行的第j-k个元素之和 
int sumSquare(int rlow,int rhigh,int clow,int chigh)
{
	int s=0;
	for(int i=rlow;i<=rhigh;i++){
		s+=sum[i][clow][chigh];
	}
	return s;
}
int Size(int rlow,int rhigh,int clow,int chigh)
{
	return (rhigh-rlow+1)*(chigh-clow+1);
}
int main(void) 
{
	int n,m,k;
	while(cin>>n>>m>>k)
	{
		memset(a,0,sizeof(a));
		memset(sum,0,sizeof(sum));
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>a[i][j];
			}
		}
		for(int i=1;i<=n;i++){
			for(int start=1;start<=m;start++){
				int rsum=0;
				for(int end=start;end<=m;end++){
					rsum+=a[i][end];
					sum[i][start][end]=rsum;
				}
			}
		}
		int bestSize=MAX;
		for(int rfrom=1;rfrom<=n;rfrom++){
			for(int cfrom=1;cfrom<=m;cfrom++){
				for(int rto=rfrom;rto<=n;rto++){
					for(int cto=cfrom;cto<=m;cto++){
						if(Size(rfrom,rto,cfrom,cto)<bestSize){
							if(sumSquare(rfrom,rto,cfrom,cto)>=k)
							bestSize=Size(rfrom,rto,cfrom,cto);
						}
					}
				}
			}
		}
		if(bestSize==MAX) cout<<"-1"<<endl;
		else cout<<bestSize<<endl;
	}
	return 0;
}