Description
一个r*c的墙,上面有n个位置有图,如果一张照片中有至少k张图那么这张照片合法,照片可以是任意尺寸,问有多少张不同的合法照片
Input
第一行四个整数r,c,n,k分别表示墙的大小,图片数量和合法照片中图片的数量,之后n行每行两个整数x,y表示该张图的位置(1<=r,c,n<=10,1<=k<=n)
Output
输出合法图照片的数量
Sample Input
2 2 1 1
1 2
Sample Output
4
Solution
暴力枚举所有照片,暴力统计每张照片中图的数量判合法,时间复杂度O(1e6)
Code
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define maxn 11
int r,c,n,k,m[maxn][maxn];
int main()
{
while(~scanf("%d%d%d%d",&r,&c,&n,&k))
{
memset(m,0,sizeof(m));
while(n--)
{
int x,y;
scanf("%d%d",&x,&y);
m[x][y]=1;
}
int ans=0;
for(int x1=1;x1<=r;x1++)
for(int x2=x1;x2<=r;x2++)
for(int y1=1;y1<=c;y1++)
for(int y2=y1;y2<=c;y2++)
{
int num=0;
for(int i=x1;i<=x2;i++)
for(int j=y1;j<=y2;j++)
num+=m[i][j];
if(num>=k)ans++;
}
printf("%d\n",ans);
}
return 0;
}