Cod sursa(job #1555102)

Utilizator borcanirobertBorcani Robert borcanirobert Data 22 decembrie 2015 12:06:44
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;

ifstream fin("matrix.in");
ofstream fout("matrix.out");

const int MAX = 1005;
const int MAXC = 27;
char a[MAX][MAX];
int ap[MAX][MAX];
bool el[MAX][MAX];
int b[MAXC];
int N, M;
char c[MAX];
int rez;

int main()
{
	int i, j, k;
	
	fin >> N >> M; fin.get();
	for ( i = 1; i <= N; i++ )
		fin.getline(a[i] + 1, MAX);
	
	for ( i = 1; i <= M; i++ )
	{
		fin.getline( c + 1, MAX );
		
		for ( j = 1; j <= M; j++ )
			b[c[j] - 'a']++;
	}
	
	for ( k = 0; k < 26; k++ )
	{
		memset( ap, 0, sizeof(ap) );
		for ( i = 1; i <= N; i++ )
			for ( j = 1; j <= N; j++ )
			{
				ap[i][j] = ap[i - 1][j] + ap[i][j - 1] - ap[i - 1][j - 1];
				
				if ( a[i][j] - 'a' == k )
					ap[i][j]++;
				
			//	if ( ap[i][j] )
			//	{cout << i << ' ' << j << ' ' << ap[i][j] << ' ' << b[k]; cin.get();}
				
				if ( i >= M && j >= M )
					if ( (ap[i][j] - ap[i - M][j] - ap[i][j - M] + ap[i - M][j - M]) != b[k] )
					{
						el[i][j] = true;
					//	cout << (char)(k + 'a') << ' ' << i << ' ' << j << ' ' << ap[i][j]; cin.get();
					}
			}
	}
	
	for ( i = M; i <= N; i++ )
	{
		for ( j = M; j <= N; j++ )
		{
		//	fout << el[i][j] << ' ';
			if ( !el[i][j] )
				rez++;
		}
	//	fout << '\n';
	}
	
	fout << rez << '\n';
	
	fin.close();
	fout.close();
	return 0;
}