hdu 4517
7974 ワード
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=4517
昨日のTencentのテーマ、よし、その時悲劇的にTLEが...orzさん、今日ネットで検索してみましたが、基本的にはdpで作られています...orz...
構想:sum[i][j]は1-i,1-jの行列からの'*'の個数を表す...
View Code
昨日のTencentのテーマ、よし、その時悲劇的にTLEが...orzさん、今日ネットで検索してみましたが、基本的にはdpで作られています...orz...
構想:sum[i][j]は1-i,1-jの行列からの'*'の個数を表す...
View Code
1 #include<iostream>
2 const int N=2004;
3 using namespace std;
4 char map[N][N];
5 int sum[N][N];//sum[i][j] 1-i,1-j "*"
6
7 int main(){
8 int n,m;
9 while(~scanf("%d%d",&n,&m)){
10 if(n==0&&m==0)break;
11 int x,y,count=0;
12 scanf("%d%d",&x,&y);
13 memset(sum,0,sizeof(sum));
14 for(int i=1;i<=n;i++){
15 scanf("%s",1+map[i]);
16 count=0;
17 for(int j=1;j<=m;j++){
18 if(map[i][j]=='*')count++;
19 sum[i][j]=count+sum[i-1][j];
20 }
21 }
22 count=0;
23 for(int i=1;i<=n;i++){
24 for(int j=1;j<=m;j++){
25 if(i+x-1<=n&&j+y-1<=m){
26 int ans=sum[i+x-1][j+y-1]-sum[i+x-1][j-1]-sum[i-1][j+y-1]+sum[i-1][j-1];// x*y '*'
27 if(ans==x*y)count++;
28 }
29 // x!=y!!!!
30 if(i+y-1<=n&&j+x-1<=m&&x!=y){
31 int ans=sum[i+y-1][j+x-1]-sum[i+y-1][j-1]-sum[i-1][j+x-1]+sum[i-1][j-1];
32 if(ans==x*y)count++;
33 }
34 }
35 }
36 printf("%d
",count);
37 }
38 return 0;
39 }