(DP) hdu 4517

小小明系列故事——游戏的烦恼

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 878 Accepted Submission(s): 308

Problem Description

　　小小明最近在玩一款游戏，它由n*m大小的矩阵构成，矩阵上会随机产生一些黑色的点，这些点它们可能会连在一起也可能会分开，这些点的个数没有限制，但是每个1*1方格中最多只可能有一个黑点产生。游戏要求玩家以最短的时间用x*y的小矩阵覆盖这个大矩阵，覆盖的要求有以下2点：
　　1. x*y大小的小矩阵内必须有x*y个黑点。
　　2. 多个小矩阵可以重叠，但是每个小矩阵放置的位置必须是独一无二的，即不同的小矩阵内的黑点不能完全相同。例如1*2的矩阵可以横着放，也可以竖着放，这两种方法是不同的，即使它们可能共用黑点。
　　小小明是个粗心的孩子，他尝试了很多遍都无法将所有的符合要求的小矩阵找到，聪明的你，能不能告诉烦恼中的小小明这个大矩阵里有多少个满足要求的小矩阵呢？

Input

题目有多组测试数据（不多于100个）；
每组测试数据的第一行包含2个正整数n和m，然后第二行是x和y（n，m，x，y的意思如题），接下来n行，每行m个字符，其中’ * ’表示黑点，’ . ’表示空白。
n和m为0则结束输入。

[Technical Specification]
0 < n, m <= 2000
0 < x, y <= 1000

Output

请计算并输出一共有多少个满足要求的小矩阵，每组输出占一行。

Sample Input

2 3 1 2 **. .** 0 0

Sample Output

水题啊。。直接统计额。。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int n,m,mp[2001][2001],x,y,sum[2001][2001];
char s[2001][2001];
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&m==0)
            break;
        scanf("%d%d",&x,&y);
        memset(sum,0,sizeof(sum));
        for(int i=1;i<=n;i++)
        {
            int cnt=0;
            scanf("%s",s[i]+1);
            for(int j=1;j<=m;j++)
            {
                if(s[i][j]=='*')
                    cnt++;
                sum[i][j]=sum[i-1][j]+cnt;
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(i+x-1<=n&&j+y-1<=m)
                {
                    int S=sum[i+x-1][j+y-1]-sum[i-1][j+y-1]-sum[i+x-1][j-1]+sum[i-1][j-1];
                    if(S==x*y)
                        ans++;
                }
                if(i+y-1<=n&&j+x-1<=m&&x!=y)
                {
                    int S=sum[i+y-1][j+x-1]-sum[i-1][j+x-1]-sum[i+y-1][j-1]+sum[i-1][j-1];
                    if(S==x*y)
                        ans++;
                }
            }
        }
        printf("%d
",ans);
    }
    return 0;
}