Cod sursa(job #490310)

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

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

int match (int I, int J)
{
	if (I>=n && J>=n)
	{
		for(int i=0;i<='z'-'a';++i)
			if (b[I][J][i]-b[I][J-n][i]-b[I-n][J][i]+b[I-n][J-n][i]!=x[i])
				return 0;
		return 1;
	}
	return 0;
}

void solve ()
{
	for(int i=1;i<=m;++i)
		for(int j=1;j<=m;++j)
		{
			for(int k=0;k<='z'-'a';++k)
				b[i][j][k]=b[i][j-1][k]+b[i-1][j][k]-b[i-1][j-1][k];
			++b[i][j][a[i][j]-'a'];
			if (match(i, j))++sol;
		}
}
			

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