Cod sursa(job #76234)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 8 august 2007 22:49:48
Problema Matrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
# include <stdio.h>
const long int MAXL=26;

long int atli(char a)     {return (long int)a-(long int)'a'+1;}
typedef long int SET[MAXL+1];
long int n,m;
const long int MAXN=1000; //1000
char om[MAXN+10][MAXN+10];
char vi[MAXN+10][MAXN+10];
SET seta[MAXN+1][MAXN+1],setr[MAXN+1][MAXN+1],setd[MAXN+1],settar;

void citire()
{
FILE *f=fopen("matrix.in","r");
fscanf(f,"%ld%ld",&n,&m);
char s[10000];
fgets(s,10000,f);
long int i,j;
for (i=1;i<=n;i++)
	fgets(om[i]+1,1000,f);
for (i=1;i<=m;i++)
	fgets(vi[i]+1,1000,f);
fclose(f);
}

void aduna(SET &a, SET b, long int sgn) {long int i;for (i=1;i<=MAXL;i++) a[i]+=sgn*b[i];}
int egal(SET a, SET b) {long int i;for (i=1;i<=MAXL;i++) if (a[i]!=b[i]) return 0; return 1;}

void scrie(long int sol)
{
FILE *g=fopen("matrix.out","w");
fprintf(g,"%ld\n",sol);
fcloseall();
}

void calculeaza()
{
//init setd,setr
long int i,j;
for (i=n;i>=1;i--)
for (j=n;j>=1;j--)
	{
	setr[i][j][atli(om[i][j])]++;
	if (i<=n-m+1) setd[j][atli(om[i][j])]++;
	if (j+1<=n) aduna(setr[i][j],setr[i][j+1],1);
	if (j+m<=n) aduna(setr[i][j],setr[i][j+m],-1);
	}
//init settar
for (i=1;i<=m;i++)
for (j=1;j<=m;j++)
	settar[atli(vi[i][j])]++;
for (j=n;j>=n-m+1;j--)
	aduna(seta[n-m+1][n-m+1],setd[j],1);
for (i=n-m+1;i>=1;i--)
for (j=n-m+1;j>=1;j--)
	if (i==n-m+1)
		{
	if (j<n-m+1)
		{
		aduna(seta[i][j],seta[i][j+1],1);
		aduna(seta[i][j],setd[j],1);
		aduna(seta[i][j],setd[j+m],-1);
		}
		}
	else
		{
		aduna(seta[i][j],seta[i+1][j],1);
		aduna(seta[i][j],setr[i][j],1);
		aduna(seta[i][j],setr[i+m][j],-1);
		}
long int sol=0;
for (i=1;i<=n-m+1;i++)
for (j=1;j<=n-m+1;j++)
	if (egal(seta[i][j],settar)) sol++;
scrie(sol);
}

int main()
{
citire();
calculeaza();
return 0;
}