Cod sursa(job #77899)

Utilizator peanutzAndrei Homorodean peanutz Data 15 august 2007 02:04:17
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <stdio.h>
#include <string.h>

#define NMAX 1002
#define SMAX 26

int n, m;
char a[NMAX][NMAX];
short quit[NMAX][NMAX];
int crt[NMAX][NMAX];
int nr[SMAX];
int res;

void read()
{
	int i, j;
	char s[NMAX];
	scanf("%d%d", &n, &m);
	for(i = 1; i <= n; ++i)
		scanf("%s", a[i]+1);
	for(i = 1; i <= m; ++i)
	{
		scanf("%s", s);
		for(j = 0; j < m; ++j)
			++nr[ s[j]-'a' ];
	}
}
			
int main()
{
	freopen("matrix.in", "r", stdin);
	freopen("matrix.out", "w", stdout);

	read();

	int f, i, j;

	for(f = 0; f < SMAX; ++f)
	{
		for(i = 1; i <= n; ++i)
			for(j = 1; j <= n; ++j)
			{
				crt[i][j] = crt[i-1][j] + crt[i][j-1] - crt[i-1][j-1];
				if(a[i][j]-'a' == f)
					++crt[i][j];

				if(crt[i][j] + crt[i-m][j-m] - crt[i][j-m] - crt[i-m][j] != nr[f])
					quit[i][j] = 1;

				//printf("%d ", crt[i][j]);
			}
		//printf("\n");
	}

	for(i = 1; i <= n; ++i)
	{
		for(j = 1; j <= n; ++j)
		{
			if(!quit[i][j])
					++res;
			//printf("%d ", quit[i][j]);
		}
		//printf("\n");
	}

	printf("%d\n", res);

	return 0;
}