Cod sursa(job #1248115)

Utilizator touristGennady Korotkevich tourist Data 24 octombrie 2014 18:10:28
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <cstdio>
#define Nmax 1005

using namespace std;

int n,m,fr[100],s[Nmax][Nmax];
char a[Nmax][Nmax],b[Nmax][Nmax];
bool ok[Nmax][Nmax];

int main()
{
    int i,j,sol=0,car;
    freopen ("matrix.in","r",stdin);
    freopen ("matrix.out","w",stdout);
    scanf("%d%d", &n,&m);
    for(i=1;i<=n;++i)
        scanf("%s", (a[i]+1));
    for(i=1;i<=m;++i)
        scanf("%s", (b[i]+1));
    for(i=1;i<=m;++i)
        for(j=1;j<=m;++j)
            ++fr[b[i][j]-'a'];
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j) ok[i][j]=true;
    for(car=0;car<26;++car)
    {
        for(i=1;i<=n;++i)
            for(j=1;j<=n;++j)
                s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+(a[i][j]-'a'==car);
        for(i=1;i<=n-m+1;++i)
            for(j=1;j<=n-m+1;++j)
                if(s[i+m-1][j+m-1]-s[i-1][j+m-1]-s[i+m-1][j-1]+s[i-1][j-1]!=fr[car])
                    ok[i][j]=false;
    }
    for(i=1;i<=n-m+1;++i)
        for(j=1;j<=n-m+1;++j)
            if(ok[i][j]) ++sol;
    printf("%d\n", sol);
    return 0;
}