Cod sursa(job #1000406)

Utilizator florin.elfusFlorin Elfus florin.elfus Data 22 septembrie 2013 19:59:02
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 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;
}