Cod sursa(job #478211)

Utilizator loginLogin Iustin Anca login Data 17 august 2010 20:14:36
Problema Matrix Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
# include <fstream>
# include <iostream>
# include <cstring>
# define DIM 1024
using namespace std;
int n, m, sol, x[200], a[200];
char g[DIM][DIM], v[DIM][DIM];

void read ()
{
	ifstream fin ("matrix.in");
	fin>>n>>m;
	fin.get();
	for(int i=1;i<=n;++i)
		fin.getline (g[i], DIM);
	for (int i=1;i<=m;++i)
		fin.getline (v[i], DIM);
}

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

void go (int I, int J)
{
	for(int i=(int)'a';i<=(int)'z';++i)
		a[i]=0;
	for(int i=I;i<=I+m-1;++i)
		for(int j=J;j<=J+m-1;++j)
			++a[(int)g[i][j]];
	if (match())
		++sol;
	int i=I+m, j=J+m;
	while (i<=n && j<n)
	{
		for(int k=I;k<i;++k)
			--a[(int)g[k][J]], ++a[(int)g[k+1][j]];
		for(int k=J;k<j;++k)
			--a[(int)g[I][k]], ++a[(int)g[i][k+1]];
		++a[(int)g[I][J]];
		--a[(int)g[i][j]];
		if (match())
			++sol;
		++i;++j;++I;++J;
	}
}		

void solve ()
{
	for(int i=1;i<=m;++i)
		for(int j=0;j<m;++j)
			++x[(int)v[i][j]];
	for(int i=1;i<=n-m+1;++i)
		go(i, 0);
	for(int i=1;i<n-m+1;++i)
		go(1, i);
	

}

int main ()
{
	read ();
	solve ();
	ofstream fout ("matrix.out");
	fout<<sol;
	return 0;
}