Cod sursa(job #960587)

Utilizator primulDarie Sergiu primul Data 10 iunie 2013 19:33:05
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include<stdio.h>
#include<string.h>
   
int nr,f[56];
int d[1005][1005],n;
int s[1005][1005],m;
char a[1005][1005];
   
int main ()
{
    int i,j,c;
    char car;
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    //fisiere
    scanf("%d%d\n",&n,&m);
    for(i=1;i<=n;i++ && scanf("\n"))
        for(j=1;j<=n;j++)
            scanf("%c",&a[i][j]);
    //citim harta
    for(i=1;i<=m;i++ && scanf("\n"))
        for(j=1;j<=m;j++)
        {
            scanf("%c",&car);
            f[car-'a'+1]++;
        }
    //citim virusul
    for(i=m;i<=n;i++)
        for(j=m;j<=n;j++)
            d[i][j]=1;
    //initializam toate patratele de n*n ca ar fi bune
    for(c=1;c<=26;c++)
    {
        memset(s,0,sizeof(s));
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+(a[i][j]-'a'+1==c);
        for(i=m;i<=n;i++)
            for(j=m;j<=n;j++)
                if(d[i][j] && s[i][j]-s[i-m][j]-s[i][j-m]+s[i-m][j-m]!=f[c])
                    d[i][j]=0;
    }
    //eliminam toate patratele care nu sunt bune
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            nr+=d[i][j];
    printf("%d\n",nr);
    //vedem cate patrate au ramas bune si afisam
    return 0;
}