Cod sursa(job #493294)

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

char a[1010][1010];
int m,n,upline=1,stanga=1,sum;// sum e contorul 
int vir[27],st[27],c[27],up[27],temp[27];
void read()
{
	in>>m>>n;
	
	for(int i=1;i<=m;i++)
	//in.getline(1+a[i],1005);
	for(int j=1;j<=m;j++)
		in>>a[i][j];
	
	char z;
	for(int i=1;i<=n*n;i++)//construiesc vectorul virus
	{
		in>>z;
		vir[z-'a']++;
		//out<<z<<vir[z-'a']<<endl;
	}
}
void stg(int col,int sus)
{
	for(int i=0;i<n;i++)
		
		++st [ a[sus+i] [col]-'a' ];
}
void upr(int lin,int pstg)//pstg= pozitia din stanga, de unde incep siru de n elem pe linia lin
{
	for(int i=0;i<n;i++)
		
		++up[ a[lin][pstg+i]-'a' ];
}

void current(int upline)//linia cea mai de sus; se porneste din stanga upline initial =1
{
	for(int i=0;i<n;i++)
		for(int j=1;j<=n;j++)
			c[a[i+upline][j]-'a']++;
}

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];
}

void solve()
{
	for(;(upline+n-1)<=m;++upline)
	{
		current(upline);
		upr(upline,stanga);
		
		for(;(stanga+n-1)<m;++stanga)// tre sa fie <= dar in temp nu vreau sa ies
		{
			stg(stanga,upline);
			if(compare(c,vir))
				sum++;
			for(int i=0;i<n;i++)
				temp[a[i+upline][stanga+1]-'a']++;
			add(c,temp);
			scad(c,st);
		}
		if(compare(c,vir))// asta e pt pozitia cand c (curent) e lipit de marginea dreapta a matricii a[][]
			sum++;
		stanga=1;
	}
	out<<sum;
}
void test_vir()
{
	for(int i=0;i<26;i++)
		out<<char('a'+i)<<vir[i]<<endl;
}
int main()
{
	read();
	test_vir();
//	solve();
	return 0;
}