Cod sursa(job #42958)

Utilizator pocaituDavid si Goliat pocaitu Data 29 martie 2007 17:55:20
Problema Matrix Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include<stdio.h>
#include<fstream.h>
#define nmax 1002

long m,n,v[28],t[nmax][nmax];
int long t1[nmax][nmax];
char c[nmax][nmax];
void citire()
{char d;
 int i,j;
 freopen("matrix.in","r",stdin);
 scanf("%d%d",&m,&n);
 fgets(c[0],nmax,stdin);

 for(i=0;i<m;i++)
  {
  fgets(c[i],nmax,stdin);

  }

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

void init(char s)
{int i,j;
 //memset(t,0,sizeof(t));
 for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
   {if(c[i-1][j-1]==s)
	 t[1][1]++;
	if(c[i][j-1]==s)
	 t[2][1]++;
	}
 if(t[1][1]==v[s-'a'])
   t1[1][1]|=(long)1<<(s-'a');
 if(t[2][1]==v[s-'a'])
   t1[2][1]|=(long)1<<(s-'a');

 for(i=2;i<=m-n+1;i++)
  {t[1][i]=t[1][i-1];
   for(j=1;j<=n;j++)
	 {if(c[j-1][i-2]==s)
	   t[1][i]--;
	  if(c[j-1][i+n-2]==s)
	  t[1][i]++;
	  }
   if(t[1][i]==v[s-'a'])
	 t1[1][i]|=(long)1<<s-'a';
   }


 }


void rezolva(char s)
{int i,j;
 memset(t,0,sizeof(t));
 init(s);
 for(i=2;i<=m-n+1;i++)
  for(j=(i!=2)?1:2;j<=m-n+1;j++)
   {t[i][j]=t[i-1][j]+t[i][j-1]-t[i-1][j-1];
   if(c[i-2][j-2]==s)
	 t[i][j]++;
   if(c[i+n-2][j+n-2]==s)
	 t[i][j]++;
   if(c[i-2][j+n-2]==s)
	 t[i][j]--;
   if(c[i+n-2][j-2]==s)
	 t[i][j]--;

   if(t[i][j]==v[s-'a']) t1[i][j]|=(long)1<<s-'a';
   }
 }

long numara()
{int i,j,nr=0;
 for(i=1;i<=m-n+1;i++)
  for(j=1;j<=m-n+1;j++)
   if(t1[i][j]==((long)1<<'z'-'a'+1)-1)
	 nr++;
 return nr;
 }

int main()
{char c;
 citire();
 for(c='a';c<='z';c++)
  rezolva(c);
 freopen("matrix.out","w",stdout);
 printf("%ld",numara());
 fclose(stdout);
 return 0;
 }