Hdu 4517小さなシリーズの物語——ゲームの悩み
6767 ワード
テーマ接続:http://acm.hdu.edu.cn/showproblem.php?pid=4517
第一の解法:
巡回して解く.num[i][j]はi行j列を表す前に全部でいくつありますか?×'.x*y、y*xが満たされているかどうか、x=yは一回だけ判断します.
この方法はC++を使って提出します.G++を使わないでください.でないと、タイムアウトします.
第二の方法:
二次元DPですが、MLEができます.
第三種類:
スクロール配列に変えて、一次元DPになります.
第一の解法:
巡回して解く.num[i][j]はi行j列を表す前に全部でいくつありますか?×'.x*y、y*xが満たされているかどうか、x=yは一回だけ判断します.
この方法はC++を使って提出します.G++を使わないでください.でないと、タイムアウトします.
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
int map[2005][2005];
int num[2005][2005];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int n,m,x,y;
while(scanf(" %d %d",&n,&m)!=EOF)
{
if(n+m == 0) break;
for(int i=0;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
num[i][j] = 0;
}
}
scanf(" %d %d",&x,&y);
getchar();
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
char c;
scanf("%c",&c);
if(c == '*')
{
map[i][j] = 1;
}
else
{
map[i][j] = 0;
}
}
getchar();
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if(map[i][j] == 1)
{
num[i][j] = num[i-1][j] + num[i][j-1] - num[i-1][j-1] + 1;
}
else
{
num[i][j] = num[i-1][j] + num[i][j-1] - num[i-1][j-1];
}
}
}
int ans = 0;
int size = x*y;
for(int i=x; i<=n; i++)
{
for(int j=y; j<=m; j++)
{
// x*y
if(num[i][j] - num[i-x][j] - num[i][j-y] + num[i-x][j-y] == size)
{
ans++;
}
}
}
if(x!=y)
{
for(int i=y; i<=n; i++)
{
for(int j=x; j<=m; j++)
{
// x*y
if(num[i][j] - num[i-y][j] - num[i][j-x] + num[i-y][j-x] == size)
{
ans++;
}
}
}
}
printf("%d
",ans);
}
return 0;
}
第二の方法:
二次元DPですが、MLEができます.
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
int map[2005][2005];
int h[2005][2005];
int l[2005][2005];
int l2[2005][2005];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int n,m,x,y;
while(scanf(" %d %d",&n,&m)!=EOF)
{
if(n+m == 0) break;
memset(h,0,sizeof(h));
memset(l,0,sizeof(l));
memset(l2,0,sizeof(l2));
scanf(" %d %d",&x,&y);
getchar();
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
char c;
scanf("%c",&c);
if(c == '*')
map[i][j] = 1;
else
map[i][j] = 0;
}
getchar();
}
int ans = 0;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if(map[i][j] == 1)
{
h[i][j] = h[i-1][j] + 1;
if(h[i][j]>=x)
l[i][j] = l[i][j-1] + 1;
else
l[i][j] = 0;
if(h[i][j]>=y)
l2[i][j] = l2[i][j-1] + 1;
else
l2[i][j] = 0;
if(h[i][j]>=x && l[i][j]>=y)
ans++;
if(h[i][j]>=y && l2[i][j]>=x && x!=y)
ans++;
}
else
{
h[i][j] = l[i][j] = l2[i][j] = 0;
}
}
}
printf("%d
",ans);
}
return 0;
}
第三種類:
スクロール配列に変えて、一次元DPになります.
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
int map[2005][2005];
int h[2005];
int l[2005];
int l2[2005];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int n,m,x,y;
while(scanf(" %d %d",&n,&m)!=EOF)
{
if(n+m == 0) break;
memset(h,0,sizeof(h));
memset(l,0,sizeof(l));
memset(l2,0,sizeof(l2));
scanf(" %d %d",&x,&y);
getchar();
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
char c;
scanf("%c",&c);
if(c == '*')
map[i][j] = 1;
else
map[i][j] = 0;
}
getchar();
}
int ans = 0;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if(map[i][j] == 1)
{
h[j] = h[j] + 1;
if(h[j]>=x)
l[j] = l[j-1] + 1;
else
l[j] = 0;
if(h[j]>=y)
l2[j] = l2[j-1] + 1;
if(h[j]>=x && l[j]>=y)
ans++;
if(h[j]>=y && l2[j]>=x && x!=y)
ans++;
}
else
{
h[j] = l[j] = l2[j] = 0;
}
}
}
printf("%d
",ans);
}
return 0;
}