Cod sursa(job #492056)

Utilizator Teodor94Teodor Plop Teodor94 Data 13 octombrie 2010 12:22:18
Problema Matrix Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<cstdio>

const int N=1005;
const int M=30;

int a[N][N],m,n,fra[M],frb[M],sum[N][N][M];

void citmat(int &m,int a[N][N])
{
	char s[N];
	for (int i=1;i<=m;++i)
	{
		gets(s);
		for (int j=0;j<m;++j)
			a[i][j+1]=s[j]-'a';
	}
}

void citire()
{
	freopen("matrix.in","r",stdin);
	freopen("matrix.out","w",stdout);
	scanf("%d%d",&m,&n);
	citmat(m,a);
}

void calculc()
{
	char x[N];
	for (int i=1;i<=n;++i)
	{
		gets(x+1);
		for (int j=1;j<=n;++j)
		{
			if(i<n && j<n)
				fra[a[i][j]]++;
			frb[x[j]-'a']++;
		}
	}
}

void actualfra(int i1,int i2)
{
	for (int j=1;j<n;++j)
	{
		fra[a[i2][j]]++;
		fra[a[i1-1][j]]--;
	}
}

void cop(int a,int b)
{
	for (int k=0;k<26;++k)
		sum[a][b][k]=sum[a][b-1][k];
}

void calculsum()
{
	for (int j=1;j<=m;++j)
		sum[1][j][a[1][j]]++;
	for (int i=2;i<=m;++i)
		for (int j=1;j<=m;++j)
		{
			cop(i,j);
			sum[i][j][a[i][j]]++;
		}
}

bool verif()
{
	for (int i=0;i<26;++i)
		if (fra[i]!=frb[i])
			return false;
	return true;
}

void actual()
{
	int i1,i2,c1,c2;
	for (i1=1,i2=n;i2<m;++i1,++i2)
		for (c1=1,c2=n;c2<m;++c1,++c2)
			for (int k=0;k<26;++k)
				fra[k]+=sum[i2][c2+1][k]-sum[i1-1][c2+1][k]-(sum[i2][c1][k]-sum[i1-1][c1][k]);
}

int main()
{
	citire();
	calculc();
	int i1,i2,j1,j2,nr=0;
	for (i1=1,i2=n;i2<m;++i1,++i2)
	{
		actualfra(i1,i2);
		for (j1=1,j2=n;j2<=m;++j1,++j2)
		{
			actual();
			if (verif())
				++nr;
		}
	}
	printf("%d\n",nr);
	return 0;
}