首页 > 代码库 > 一个N*M的矩阵，找出这个矩阵中所有元素的和不小于K的面积最小的子矩阵
一个N*M的矩阵，找出这个矩阵中所有元素的和不小于K的面积最小的子矩阵
- 题目描述：
一个N*M的矩阵，找出这个矩阵中所有元素的和不小于K的面积最小的子矩阵（矩阵中元素个数为矩阵面积）
- 输入：
每个案例第一行三个正整数N,M<=100，表示矩阵大小，和一个整数K
接下来N行，每行M个数，表示矩阵每个元素的值
- 输出：
输出最小面积的值。如果出现任意矩阵的和都小于K，直接输出-1。
- 样例输入：
4 4 101 2 3 45 6 7 89 10 11 1213 14 15 16
- 样例输出：
1
首先这个题应该是有一个动态规划的解法，不过好像复杂度也要到O(n^3logn)，所以这里直接暴力了。但是为了节省时间首先计算出从左上角开始的矩阵的和，然后根据这个和可以求各个矩阵的值
1 //计算左上角为(1,1)的所有子矩阵的和，需要O(N^2)的时间。 2 //此时只需要O(1)的时间就可以算出每个子矩阵的和。 3 //枚举次数依然不变。总时间复杂度为O(N^4) 4 #include<iostream> 5 #include<cstdio> 6 #include<cstring> 7 using namespace std; 8 int main() 9 {10 //freopen("t","r",stdin);11 int m,n,k;12 while(cin>>m>>n>>k){13 int ma[105][105];14 for(int i=0;i<m;i++){15 for(int j=0;j<n;j++){16 cin>>ma[i][j];17 }18 }19 int sum[105][105];20 memset(sum,0,sizeof(sum));21 sum[0][0]=ma[0][0];22 for(int i=1;i<m;i++){23 sum[i][0]=ma[i][0]+sum[i-1][0];24 }25 for(int i=1;i<n;i++){26 sum[0][i]=ma[0][i]+sum[0][i-1];27 }28 for(int i=1;i<m;i++){29 for(int j=1;j<n;j++){30 sum[i][j]+=sum[i][j-1];31 for(int k=0;k<=i;k++){32 sum[i][j]+=ma[k][j];33 }34 }35 }36 37 int minsize=999999;38 for(int a=0;a<m;a++){39 for(int b=a;b<m;b++){40 for(int c=0;c<n;c++){41 for(int d=c;d<n;d++){42 int s=0;43 if(a==0&&b==0&&c==0&&d==0){44 s=sum[0][0];45 }46 else if(a==0&&c==0){47 s=sum[b][d];48 }49 else if(a==0){50 s=sum[b][d]-sum[b][c-1];51 }52 else if(c==0){53 s=sum[b][d]-sum[a-1][d];54 }55 else{56 s=sum[b][d]+sum[a-1][c-1]-sum[a-1][d]-sum[b][c-1];57 }58 if(s>=k){59 int sizee=(b-a+1)*(d-c+1);60 if(minsize>sizee){61 minsize=sizee;62 }63 }64 }65 }66 }67 }68 if(minsize==999999){69 cout<<-1<<endl;70 }71 else{72 cout<<minsize<<endl;73 }74 }75 return 0;76 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。