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

本文地址：http://uwind.iteye.com/blog/1922844

题目大意：

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

题目有多组测试数据（不多于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

解题报告：

首先看这题的数据范围，显然要求用m*n的方法过这题。

根据以往的经验，可以按行DP。

统计以第i行为底的向上最多能累计多少个星星。

 

然后生成一个序列h

然后再查找序列h中连续一段高度比x要大的。这一段长度记为len

如果len>=y答案就加上len-y+1

 

总的复杂度是O(n*m)

#include<stdio.h>
#include<string.h>
const int MAX=2100;
char map[MAX][MAX];
int h[MAX];
int calc(int n,int x,int y)
{
    int i,cnt=0,j;
    int ret=0;
    for(i=0;i<n;i++)
    {
        if(h[i]>=x)
        {
            cnt=0;
            j=i;
            while(j<n&&h[j]>=x)
            {
                cnt++;
                j++;
            }
            i=j-1;
            if(cnt>=y)ret+=cnt-y+1;
        }
    }
    return ret;
}
int main(){
    int n,i,j;
    int m;
    int x,y;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&m==0)break;
        scanf("%d%d",&x,&y);
        for(i=0;i<n;i++)
        {
            scanf("%s",map[i]);
        }
        memset(h,0,sizeof(h));
          
        int ans=0;
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                if(map[i][j]=='*')
                {
                    h[j]++;
                }
                else
                {
                    h[j]=0;
                }
            }
  
            ans+=calc(m,x,y);
            if(x!=y)ans+=calc(m,y,x);
        }
  
        printf("%d\n",ans);
    }
    return 0;

}