题意：
给定n*m的图，和一个整数k， 图由’X‘和’.‘组成，现在要求你找到一个面积最小的子矩阵，满足子矩阵中的’.'不少于k个。 输出最小面积。
数据范围：n,m<=300，k<=n*m
解法：
考虑1*m的矩阵，如果要求找到一个最小的子矩阵，满足不少于k个， 可以直接尺取。
那么n*m怎么做呢，枚举行i和行j，将[i,j]行合并为一行，每一列是[i,j]列的权值和。 然后就变成上面的情况了，进行尺取即可。
枚举i,j的复杂度为O(n2)，尺取O(n)，总复杂度O(n3)
code：
#include<bits/stdc++.h>
using namespace std
;
#define int long long
#define ll long long
#define PI pair<int,int>
const int maxm
=305;
char s
[maxm
][maxm
];
int sum
[maxm
][maxm
];
int temp
[maxm
];
int a
[maxm
];
int n
,m
,k
;
signed main(){
ios
::sync_with_stdio(0);
while(cin
>>n
>>m
>>k
){
if(!(n
+m
+k
))break;
for(int i
=1;i
<=n
;i
++){
for(int j
=1;j
<=m
;j
++){
cin
>>s
[i
][j
];
}
}
for(int i
=1;i
<=n
;i
++){
for(int j
=1;j
<=m
;j
++){
sum
[i
][j
]=sum
[i
][j
-1]+sum
[i
-1][j
]-sum
[i
-1][j
-1]+(s
[i
][j
]=='.');
}
}
int ans
=n
*m
;
for(int i
=1;i
<=n
;i
++){
for(int j
=i
;j
<=n
;j
++){
for(int t
=1;t
<=m
;t
++){
temp
[t
]=sum
[j
][t
]-sum
[i
-1][t
];
}
int p
=1;
for(int t
=1;t
<=m
;t
++){
while(temp
[t
]-temp
[p
-1]>=k
){
ans
=min(ans
,(j
-i
+1)*(t
-p
+1));
p
++;
}
}
}
}
cout
<<ans
<<endl
;
}
return 0;
}
