Cod sursa(job #385467)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 22 ianuarie 2010 19:38:51
Problema Matrix Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <cstdio>
#include <cstring>

#define file_in "matrix.in"
#define file_out "matrix.out"

#define Nmax 1010

int n,m,i,j,sol,k,l,ii,jj;
int f[27];
char s[Nmax];
int frecv[27];
char a[Nmax][Nmax];
int T[Nmax][Nmax];

int main()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d\n", &n, &m);
	for (i=1;i<=n;++i)
	{
		fgets(s,Nmax,stdin);
		for (j=0;j<n;++j)
			 a[i][j+1]=s[j];
	}
	memset(frecv,0,sizeof(frecv));
	for (i=0;i<m;++i)
	{
		fgets(s,Nmax,stdin);
		for (j=0;j<m;++j)
			 frecv[s[j]-'a']++;
	}
	
	if (n<=200)
	{
		
	sol=0;
	
	for (i=1;i<=n;++i)
		 for (j=1;j<=n;++j)
		 {
			 memset(f,0,sizeof(f));
			 int ok=0;
	         for (k=i;k<=i+m-1 && !ok;++k)
	              for (l=j;l<=j+m-1 && !ok;++l)
					{
						int x=a[k][l]-'a';
						f[x]++;
						if (frecv[x]<f[x]) ok=1;
				  }
			if (!ok) sol++;
		 }						
					   
	printf("%d\n", sol);
	
	return 0;
	}
	
	for (i=1;i<=n;++i)
		 for (j=1;j<=n;++j)
		 	 T[i][j]=T[i-1][j]+T[i][j-1]-T[i-1][j-1]+1;
	
	for (i=1;i<=n;++i)
		 for (j=1;j<=m;++j)
		 {
			 int ok=0;
			 for (k=0;k<26 && !ok;++k)
				  if (frecv[a[k][l]-'a']!=(T[i][j]-T[i-m][j]-T[i][j-m]+T[i-m][j-m]))
					  ok=1;
				if (!ok) sol++;
		 }

	printf("%d\n", sol);	 
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}