杭電ACM 4517小明シリーズの物語--ゲームの悩み

本住所:http://uwind.iteye.com/blog/1922844
テーマ:
小さい明は最近1種のゲームを遊んで、それはn*mの大きさの行列から構成して、行列の上でランダムにいくつかの黒い点を生んで、これらの点はそれらがつながっても分けることができて、これらの点の個数は制限がなくて、しかし1*1の四角形の中で最大で1つの黒い点が発生することができます.ゲームはプレイヤーに最短時間でx*yの小行列でこの大行列をカバーすることを要求し、カバーする要求は以下の2点がある:1. x*yサイズの小さなマトリクスにはx*y個の黒点が必要です.　　2. 複数の小さなマトリクスは重なり合うことができるが、各小さなマトリクスが配置される位置はユニークでなければならない.すなわち、異なる小さなマトリクス内の黒点は完全に同じではない.例えば、1*2のマトリクスは、黒点を共有していてもよいし、縦に配置してもよい.明ちゃんは不注意な子で、何度も何度も要求に合った小さな行列を見つけることができませんでした.頭のいいあなたは、悩みの中の明ちゃんという大きな行列の中に何個要求を満たす小さな行列があるか教えてくれませんか.
テーマには複数のテストデータ(100個未満)があります.各テストデータのセットの最初の行は2つの正の整数nとmを含み、次いで2番目の行はxとy(n,m,x,yの意味は問題のように)、次のn行、各行m文字、そのうち’ * ’黒点を表す . ’空白を表す.nとmが0の場合は入力を終了します.[Technical Specification]0 < n, m <= 20000 < 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
",ans);
    }
    return 0;

}