Cod sursa(job #832726)

Utilizator elfusFlorin Chirica elfus Data 11 decembrie 2012 11:04:52
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <stdio.h>
 
char x[1024][1024];
int dp[1024][1024], frequence[30];
bool good[1024][1024];
 
int main()
{
    int i, j, letter, N, M;
     
    freopen("matrix.in", "r", stdin);
    freopen("matrix.out", "w", stdout);
     
    scanf("%d%d\n", &N, &M);
    for (i = 1; i <= N; i ++)
        gets(x[i] + 1);
     
    char ch;
    for (i = 1; i <= M; i ++, scanf("\n"))
        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;
         
    for (letter = 0; letter <= 25; letter ++)
        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 (x[i][j] == letter + 'a')
                    dp[i][j] ++;
                if (good[i][j])
                {
                    int now = dp[i][j] - dp[i - M][j] - dp[i][j - M] + dp[i - M][j - M];
                    if (now != frequence[letter])
                        good[i][j] = false;
                }
            }
     
    int sol = 0;
    for (i = 1; i <= N; i ++)
        for (j = 1; j <= N; j ++)
            sol += good[i][j];
     
    printf("%d", sol);
    return 0;
}