Cod sursa(job #490292)

Utilizator loginLogin Iustin Anca login Data 5 octombrie 2010 20:52:42
Problema Matrix Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
# include <fstream>
# include <iostream>
# define DIM 1024
using namespace std;
int n, m, x[30], v[40], sol;
char a[DIM][DIM];

void read ()
{
	ifstream fin ("matrix.in");
	fin>>m>>n;
	fin.get();
	for(int i=0;i<m;++i)
		fin.getline(a[i], DIM);
	char c;
	for(int i=1;i<=n;++i)	
		for(int j=1;j<=n;++j)
		{
			fin>>c;
			++x[c-'a'];
		}
}

int match ()
{
	for(int i=0;i<='z'-'a';++i)
		if (v[i]!=x[i])
			return 0;
	return 1;
}

void go (int I, int J)
{
	for (int i=0;i<='z'-'a';++i)v[i]=0;
	for(int i=I;i<I+n;++i)
		for(int j=J;j<J+n;++j)
			++v[a[i][j]-'a'];
	if (match())++sol;
	while (I+n<m && J+n<m)
	{
		for(int i=I;i<=I+n-1;++i)--v[a[i][J]-'a'];
		for(int j=J+1;j<=J+n-1;++j)--v[a[I][j]-'a'];
		for(int i=I+1;i<=I+n;++i)++v[a[i][J+n]-'a'];
		for(int j=J+1;j<J+n;++j)++v[a[I+n][j]-'a'];
		if (match())++sol;
		++I;++J;
	}
}
		
int main()
{
	read ();
	for(int i=0;i<=m-n;++i)	
		go(0, i);
	for(int i=1;i<=m-n;++i)
		go(i, 0);
	ofstream fout ("matrix.out");
	fout<<sol;
	return 0;
}