Cod sursa(job #1722147)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 27 iunie 2016 14:22:38
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdio>
#include <algorithm>
#define MAX 6000000
#define INF 2000000005
using namespace std;
char f[MAX],Matrix[1005][1005],C;
int pos=0,N,M,mat[1005][1005]={},v[30],S=0;
bool places[1005][1005];
void r(int &nr)
{
    nr=0;
    while(f[pos]<'0'||f[pos]>'9')
		pos++;
    while(f[pos]>='0'&&f[pos]<='9')
        nr=nr*10+f[pos++]-'0';
}
void rch(char &ch)
{
    while(f[pos]<'a'||f[pos]>'z')
        pos++;
    ch=f[pos++];
}
int main()
{
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout); 
	fread(f,1,MAX,stdin);
	r(M),r(N);
	for(int i=1;i<=M;i++)
		for(int j=1;j<=M;j++)
		{	
			rch(Matrix[i][j]);
			if(i>=N&&j>=N)places[i][j]=true;
		}
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
		{	rch(C);
			v[C-'a'+1]++;
		}
	for(char c='a';c<='z';c++)
	{
		int mat[1005][1005]={};
		for(int i=1;i<=M;i++)
			for(int j=1;j<=M;j++)
			{
				mat[i][j]=mat[i-1][j]+mat[i][j-1]-mat[i-1][j-1];
				if(Matrix[i][j]==c)
					mat[i][j]++;
				if(i>=N&&j>=N&&places[i][j]==true)
					if(!(mat[i][j]-mat[i-N][j]-mat[i][j-N]+mat[i-N][j-N]==v[c-'a'+1]))
						places[i][j]=false;
			}
	}
	for(int i=1;i<=M;i++)
		for(int j=1;j<=M;j++)
			if(places[i][j]==true)
				S++;
	printf("%d",S);
	return 0;
}