Cod sursa(job #492054)

Utilizator nightwish0031Vlad Radu Cristian nightwish0031 Data 13 octombrie 2010 12:17:53
Problema Matrix Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<cstdio>

const int NMAX=1<<10;

int m1[NMAX][NMAX];
int f2[27];
int f1[27];
int M,N;
int sumc[NMAX][NMAX][26];

void fisiere()
{
	freopen("matrix.in","r",stdin);
	freopen("matrix.out","w",stdout);
}

void citeste()
{
	fisiere();
	
	int i,j;
	char s[NMAX];
	
	scanf("%d%d",&M,&N);

	for (i=1;i<=M;++i)
	{
		gets(s);
		for (j=0;j<M;++j)
			m1[i][j+1]=s[j]-'a';
	}
	
	for (i=1;i<=N;++i)
	{
		gets(s);
		for (j=0;j<N;++j)
			++f2[s[j]-'a'];
	}
}

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


void sumpart()
{
	int j,i;
	
	for (j=1;j<=M;++j)
		sumc[1][j][m1[1][j]]++;
	
	
	for (i=2;i<=M;++i)
		for (j=1;j<=M;++j)
		{
			cop(i,j);
			sumc[i][j][m1[i][j]]++;
		}
}

bool egalitate()
{
	int i;
	for (i=0;i<26;++i)
		if (f1[i]!=f2[i]) 
			return false;
	return true;
}

void actualizare(int c1,int c2,int i2)
{	
	int k;
	for (k=0;k<26;++k)
		f1[k]+=sumc[i2][c2][k]-sumc[i2][c1][k];	
}

void actualizare2(int i1,int i2)
{
	int j,k;
	for (j=1;j<=N;++j)
		for (k=0;k<26;++k)
			f1[k]-=sumc[i1][j][k]-sumc[i1-1][j][k]+sumc[i2][j][k]-sumc[i2-1][j][k];
}


void afiseaza(int numar)
{
	printf("%d",numar);
}
void rezolva()
{
	
	int numar, c1,c2, i1,i2, i,j;
	numar=0;
	
	for (i=1;i<=N;++i)
		for (j=1;j<=N;++j)
			f1[m1[i][j]]++;
	
	i1=1;
	i2=N;

	do
	{
		c1=1;
		c2=N;
		
		do
		{
			if (egalitate()==true) ++numar;
			++c2;
			actualizare(c1,c2,i2);
			++c1;
		}while(c2<=M);

		++i2;
		actualizare2(i1,i2);
		++i1;	
		
	}while(i2<=M);

	afiseaza(numar);
}

int main()
{
	citeste();
	sumpart();
	rezolva();
	
	return 0;
}