Cod sursa(job #269570)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 3 martie 2009 00:30:20
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
# include <stdio.h>
# include <string.h>

const long int MAXN=1000;

long int count[MAXN+1][MAXN+1],match[MAXN+1][MAXN+1],n,m,count_temp[256];
char a[MAXN+1][MAXN+1],temp[MAXN+1][MAXN+1];

void citire()
{
     FILE *f=fopen("matrix.in","r");
     fscanf(f,"%ld%ld",&n,&m);
     long int i,j;
     for (i=1;i<=n;i++)
     for (j=1;j<=n;j++)
         do
         {a[i][j]=fgetc(f);}
         while (a[i][j]>'z'||a[i][j]<'a');
     for (i=1;i<=m;i++)
     for (j=1;j<=m;j++)
         do
         {temp[i][j]=fgetc(f);}
         while (temp[i][j]>'z'||temp[i][j]<'a');
     fclose(f);
}

void scrie(long int sol)
{
     FILE *g=fopen("matrix.out","w");
     fprintf(g,"%ld\n",sol);
     fclose(g);
}

void calculeaza()
{
     char c;
     long int i,j;
     for (c='a';c<='z';c++)
         {
         //calculam count
         for (i=1;i<=n;i++)
             for (j=1;j<=n;j++)
                 {
                 count[i][j]=count[i-1][j]+count[i][j-1]-count[i-1][j-1];
                 if (c==a[i][j]) count[i][j]++;
                 //verificam eventual o potrivire
                 if (i>=m&&j>=m)
                 if (match[i][j]==0)
                    if (count[i][j]-count[i-m][j]-count[i][j-m]+count[i-m][j-m]!=count_temp[c])
                       {
                       match[i][j]=1;
                       match[0][0]--;
                       }
                 }
         }
}

int main()
{
    citire();   
    
    //init
    match[0][0]=(n-m+1)*(n-m+1);
    long int i,j;
    for (i=1;i<=m;i++)
    for (j=1;j<=m;j++)
        count_temp[temp[i][j]]++;
    calculeaza();
    scrie(match[0][0]);
    
    //getchar();
    return 0;
}