Cod sursa(job #10848)

Utilizator crawlerPuni Andrei Paul crawler Data 29 ianuarie 2007 19:35:43
Problema Matrix Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 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;
   register char c;

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

   for(i=1;i<=n;++i)
     for(j=1;j<=n;++j)
      {
       scanf("%c", &c);
       v[i][j]=c-97;
      }

   for(i=1;i<=m;++i)
    for(j=1;j<=m;++j)
     {
      scanf("%c", &c);
      ++x[c-97];
     }


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

  for(k=0;k<=24;++k)
   {
    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] + (v[i][j]==k);
   
    for(i=m;i<=n;++i)
     for(j=m;j<=n;++j)
      if(!st[i][j] && S(i,j,m)!=x[k])
       {
        st[i][j]=1;
        --T;
       }
   }

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

   return 0;
 }