Cod sursa(job #10861)

Utilizator crawlerPuni Andrei Paul crawler Data 29 ianuarie 2007 19:55:19
Problema Matrix Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <stdio.h>

long v[1024][1024], s[1024][1024], x[26];
char st[1024][1024];

long S(long i,long j,long m)
 {
  return s[i][j]-s[i-m][j]-s[i][j-m]+s[i-m][j-m];
 }

int main()
 {
   freopen("matrix.in","r",stdin);
   freopen("matrix.out","w",stdout);

   register long i,j,k, n,m, T=0;
   char c[1024];

   scanf("%ld%ld\n", &n,&m);

   for(i=1;i<=n;++i)
    {
     fgets(c,1001,stdin);
     for(j=0;j<n;++j)
       v[i][j]=c[j]-97;
    }

   for(i=1;i<=m;++i)
    {
     fgets(c,1001,stdin);
     for(j=0;j<m;++j)
      ++x[c[j]-97];
    }

  T=n-m+1;
  T*=T;

  for(k=0;k<=25;++k)
   {
    for(i=1;i<=n;++i)
     for(j=0;j<n;++j)
      s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + (v[i][j]==k);
   
    for(i=m;i<=n;++i)
     for(j=m-1;j<n;++j)
      if((!st[i][j]) && (S(i,j,m)!=x[k]))
       {
        st[i][j]=1;
        --T;
       }
   }

   printf("%ld\n", T);

   return 0;
 }