Cod sursa(job #87636)

Utilizator andrei_infoMirestean Andrei andrei_info Data 27 septembrie 2007 22:39:15
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdlib>
#include <cstdio>
#include <cstring>


//infoarena matrix 178

#define MAX 1001
char a[MAX][MAX], b[MAX][MAX];
int t[MAX][MAX], lit[26], N, M, nrmat;
bool rez[MAX][MAX];

void citire()
{
    freopen("matrix.in", "r", stdin);
    scanf("%d%d\n", &M, &N);

    for (int i = 1; i<=M; i++)
    {
        for (int j = 1; j<=M; j++)
            scanf("%c", &a[i][j]);
        scanf("\n");
    };
    for (int i = 1; i<=N; i++)
    {
        for (int j = 1; j<=N; j++)
        {
            scanf("%c", &b[i][j]);
            lit[b[i][j]-'a']++;
        }
        scanf("\n");
    };
    fclose(stdin);
};


void calc()
{
    for (int c = 'a'; c<='y'; c++)
    {
        memset(t,0,sizeof(t));
        for (int i = 1; i<=M; i++)
            for (int j = 1; j<=M; j++)
            {
                t[i][j] = t[i-1][j]+t[i][j-1] - t[i-1][j-1];
                if (a[i][j] == c) t[i][j]++;
            };

        for (int i = N; i<=M; i++)
            for (int j = N; j<=M; j++)
            {
                int x= t[i][j] - t[i-N][j]- t[i][j-N]+t[i-N][j-N];
                if ( x != lit[c-'a'] )
                    rez[i][j] = 1;
            };
    };
    for (int i = N; i<=M; i++)
        for (int j=N; j<=M; j++)
            if (!rez[i][j])
                nrmat++;
};

int main()
{
    citire();
    calc();

    freopen("matrix.out", "w", stdout);
    printf("%d", nrmat);
    fclose(stdout);

    return 0;

};