Cod sursa(job #344565)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 30 august 2009 16:14:19
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <stdio.h>
#define Nmax 1005

char a[Nmax][Nmax],b[Nmax][Nmax];
int t[Nmax][Nmax],all[Nmax][Nmax];
int cnt[30];
int n,m;

void read(){
	int i,j;
	freopen("matrix.in","r",stdin);
   freopen("matrix.out","w",stdout);
   scanf("%d%d\n",&m,&n);
   for(i=1;i<=m;++i){
     for(j=1;j<=m;++j) scanf("%c",&a[i][j]);
     scanf("\n");
   }
   for(i=1;i<=n;++i){
     for(j=1;j<=n;++j){
     	 scanf("%c",&b[i][j]);
       cnt[b[i][j]-'a']++;
     }
     scanf("\n");
   }
}

void work(){
	int i,j; char c;
   int nr,sol=0;
   for(i=n;i<=m;++i)
     for(j=n;j<=m;++j) all[i][j]=1;
   for(c='a'; c<='z'; c++)
   	if(cnt[c-'a']!=0){
       for(i=1;i<=m;++i)
         for(j=1;j<=m;++j){
           t[i][j]=t[i-1][j]+t[i][j-1]-t[i-1][j-1]+(a[i][j]==c);
           // pt matricea cu colturi (i-n+1) (j-n+1)
           if( i-n>=0 && j-n>=0 ){
              nr = t[i][j]-t[i-n][j]-t[i][j-n]+t[i-n][j-n];
              if(nr < cnt[c-'a']) all[i][j]=0;
           }
           else all[i][j]=0;
         }
       }                                        

   for(i=n;i<=m;++i)
     for(j=n;j<=m;++j) sol+=all[i][j];
   printf("%d\n",sol);
   fclose(stdin); fclose(stdout);
}

int main(){
	read();
   work();
   return 0;
}