Cod sursa(job #1760012)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 20 septembrie 2016 09:20:39
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include<bits/stdc++.h>
#define maxN 1005
using namespace std;
int a[maxN][maxN],mat[maxN][maxN],s[maxN][maxN],n,m,frecv[350],f,ap;
bool seen[maxN][maxN];
int main()
{
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("\n");
        for(int j=1;j<=n;j++)
        {
            scanf("%c",&a[i][j]);
        }
    }
    for(int i=1;i<=m;i++)
    {
        scanf("\n");
        for(int j=1;j<=m;j++)
        {
            scanf("%c",&mat[i][j]);
            frecv[mat[i][j]]++;
        }
    }
    /*for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=m;j++) printf("%c ",mat[i][j]);
        printf("\n");
    }*/

    for(int c='a';c<='z';c++)
    {
        s[1][1]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+(a[i][j]==c);
                if (i>=m && j>=m)
                {
                    f=s[i][j]-s[i][j-m]-s[i-m][j]+s[i-m][j-m];
                    if (f!=frecv[c])
                    {
                        seen[i][j]=1;
                    }
                }
            }
        }
    }
    for(int i=m;i<=n;i++)
    {
        for(int j=m;j<=n;j++)
        {
            if (!seen[i][j]) ap++;
        }
    }
    printf("%d\n",ap);
    return 0;
}