Cod sursa(job #832654)

Utilizator elfusFlorin Chirica elfus Data 11 decembrie 2012 00:41:20
Problema Matrix Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <stdio.h>

char x[1024][1024], frequence[30];
int dp[1024][1024];
bool good[1024][1024];

int main()
{
	int i, j, k, letter, N, M;
	char ch;
	
	freopen("matrix.in", "r", stdin);
	freopen("matrix.out", "w", stdout);
	
	scanf("%d%d\n", &N, &M);
	for (i = 1; i <= N; i ++)
		for (j = 1; j <= N; j ++)
			scanf(" %c ", &x[i][j]);
	
	for (i = 1; i <= M; i ++)
		for (j = 1; j <= M; j ++)
		{
			scanf(" %c ", &ch);
			frequence[ch - 'a'] ++;
		}
	for (i = M; i <= N; i ++)
		for (j = M; j <= N; j ++)
			good[i][j] = true;
	
	//Fragment copiat ca sa vad daca aici e problema
	int n = N, m = M;
	for( k=0;k<26;k++)
    {
        for( i=1;i<=n;i++)
            for( j=1;j<=n;j++)
            {
                dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
                if(k==(x[i][j]-'a'))
                    ++dp[i][j];
 
                if(i-m>=0 && j-m>=0 && frequence[k]==( dp[i][j]-dp[i-m][j]-dp[i][j-m]+dp[i-m][j-m]))
                        good[i][j]*=1;
                    else
                        good[i][j]=0;
            }
    }
	
	int sol = 0;
	for (i = M; i <= N; i ++)
		for (j = M; j <= N; j ++)
			if (good[i][j])
				sol ++;
	
	printf("%d", sol);
	return 0;
}