Cod sursa(job #1970831)

Utilizator andru47Stefanescu Andru andru47 Data 19 aprilie 2017 17:21:00
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1005;
int m , n, ap[30] , dp1[NMAX][NMAX], dp2[NMAX][NMAX];
char a[NMAX][NMAX];
int main()
{
    freopen("matrix.in", "r", stdin);
    freopen("matrix.out", "w", stdout);

    scanf("%d %d\n", &m, &n);
    for (int i = 1; i<=m; ++i)
        gets(a[i] + 1);
    for (int i = 1; i<=n; ++i)
    {
        char chr;
        for (int j = 1; j<=n; ++j)
        {
            scanf("%c", &chr);
            ++ap[chr - 'a'];
        }
        scanf("\n");
    }
    for (int litera = 0; litera < 26; ++litera)
    {
        for (int i = 1; i<=m; ++i)
            for (int j = 1; j<=m; ++j)
                dp1[i][j] = dp1[i - 1][j] + dp1[i][j - 1] - dp1[i - 1][j - 1] + (a[i][j] - 'a' == litera);
        for (int i = n; i<=m; ++i)
            for (int j = n; j<=m; ++j)
                if (dp1[i][j] + dp1[i - n][j - n] - dp1[i - n][j] - dp1[i][j - n] != ap[litera])
                    dp2[i][j] = 1;
        memset(dp1, 0 , sizeof(dp1));
    }
    int ret = 0;
    for (int i = n; i<=m; ++i)
        for (int j = n; j<=m; ++j)
            ret += !dp2[i][j];
    printf("%d\n", ret);
    return 0;
}