Cod sursa(job #495713)

Utilizator unknownliviuMaria Liviu Valentin unknownliviu Data 26 octombrie 2010 16:48:18
Problema Matrix Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include<fstream>
using namespace std;
ifstream in("matrix.in");
ofstream out("matrix.out");

char a[1010][1010];
int sol[1010][1010][27];
int m,n; 
int vir[27];
bool compare(int A[] ,int B []);
void add(int A[], int B[]);
void scad(int A[], int B[]);
void read()
{
	in>>n>>m;
	
	for(int i=1;i<=n;i++)
	//in.getline(1+a[i],1005);
	for(int j=1;j<=n;j++)
		in>>a[i][j];
	
	char z;
	for(int i=1;i<=m*m;i++)//construiesc vectorul virus
	{
		in>>z;
		vir[z-'a']++;
	}
}
void test()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			out<<a[i][j]<<" ";
		out<<endl;
	}
}
void part1()//suma pe drept 1,1 i,j
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			add(sol[i][j] , sol[i-1][j]);
			add(sol[i][j] , sol[i][j-1]);
			scad(sol[i][j], sol[i-1][j-1]);//nu vreau sa imi dublez elemente
			sol[i][j] [a[i][j]-'a']++;
		}
}
int part2()
{
	int suma=0;
	int temp[27];
	for(int i=m;i<=n;i++)
		for(int j=m;j<=n;j++)
		{
			for(int q=0;q<26;q++)
				temp[q]=0;
			
			add(temp , sol[i-m][j-m]);
			add(temp , sol[i][j]);
			scad(temp, sol[i][j-m]);
			scad(temp, sol[i-m][j]);
			//temp=sol[i][j] -sol[i][j-m] -sol[i-m][j]  +sol[i-m][j-m] ;
			if(compare(temp,vir))
				suma++;
		}
	return suma;
}
bool compare(int A[] ,int B [])
{
	for(int i=0;i<26;i++)
		if(A[i]!=B[i])
			return false;
	return true;
}

void add(int A[], int B[])// in A[] se scrie rezultatul adunarii
{
	for(int i=0;i<26;i++)
		A[i]+=B[i];
}

void scad(int A[], int B[])//tot A[] se modifica
{
	for(int i=0;i<26;i++)
		A[i]-=B[i];
}

int main()
{
	read();
	part1();
	out<<part2();
	return 0;
}