BZOJ4624 农场种植

#include<bits/stdc++.h>
using namespace std;
struct fs
{
    double a,b;
    fs(){a=0;b=0;}
    fs(double x,double y){a=x;b=y;}
    inline fs operator * (const fs &tmp)
    {return fs(a*tmp.a-b*tmp.b,a*tmp.b+tmp.a*b);}
    inline fs operator + (const fs &tmp)
    {return fs(a+tmp.a,b+tmp.b);}
    inline fs operator - (const fs &tmp)
    {return fs(a-tmp.a,b-tmp.b);}
}A[600010],B[600010],C[600010];
double Pi=acos(-1.0);
int R[600010],lim=1,L,n,m,h,w,T,a1[510][510],a2[510][510];
char ma[510][510],bl[510][510];
void FFT(fs *D,int f)
{
    for(int i=0;i<lim;i++) if(i<R[i]) swap(D[i],D[R[i]]);
    for(int i=1;i<lim;i<<=1)
    {
        fs unit=fs(cos(Pi/i),f*sin(Pi/i));
        for(int j=0;j<lim;j+=(i<<1))
        {
            fs w=fs(1,0);
            for(int e=0;e<i;e++,w=w*unit)
            {
                fs tmp1=D[j+e],tmp2=w*D[i+j+e];
                D[j+e]=tmp1+tmp2;
                D[i+j+e]=tmp1-tmp2;
            }
        }
    }
    if(f==-1) for(int i=0;i<=lim;i++) D[i].a/=lim;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) scanf("%s",ma[i]);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            if(ma[i][j]==‘G‘) A[i*m+j].a=1;
            else B[i*m+j].a=1;
        }
    while(lim<=2*n*m) lim<<=1,L++;
    for(int i=0;i<lim;i++) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
    FFT(A,1);FFT(B,1);//for(int i=0;i<lim;i++) cout<<B[i].a<<endl;
    scanf("%d",&T);
    for(int o=1;o<=T;o++)
    {
        scanf("%d%d",&h,&w);
        memset(C,0,sizeof C);
        memset(a1,0,sizeof a1);
        memset(a2,0,sizeof a2);
        for(int i=0;i<h;i++) scanf("%s",&bl[i]);
        for(int i=0;i<h;i++)
            for(int j=0;j<w;j++) C[n*m-1-i*m-j].a=(bl[i][j]==‘G‘);
        FFT(C,1);for(int i=0;i<=lim;i++) C[i]=C[i]*A[i];FFT(C,-1);
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++) a1[i][j]=(int)(C[n*m+i*m+j-1].a+0.5);
        memset(C,0,sizeof C);
        for(int i=0;i<h;i++)
            for(int j=0;j<w;j++) C[n*m-1-i*m-j].a=(bl[i][j]==‘L‘);
        FFT(C,1);for(int i=0;i<=lim;i++) C[i]=C[i]*B[i];FFT(C,-1);
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++) a2[i][j]=(int)(C[n*m+i*m+j-1].a+0.5);
        int x=0,y=0;
        for(int i=0;i<=n-h;i++) for(int j=0;j<=m-w;j++) if(a1[i][j]+a2[i][j]>a1[x][y]+a2[x][y]) x=i,y=j;
        printf("Case #%d: %d %d %d %d\n",o,x+1,y+1,a1[x][y],a2[x][y]);
    }
}