Cod sursa(job #1260958)

Utilizator gedicaAlpaca Gedit gedica Data 11 noiembrie 2014 19:55:09
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
#include <string>
#include <cstring>

using namespace std;

ifstream in( "matrix.in" );
ofstream out( "matrix.out" );

const int NMAX= 1005;

int d[NMAX][NMAX], s[NMAX][NMAX];
char a[NMAX][NMAX];

int main(  )
{
    int N, M;
    int nr= 0, f[56]= {0};
    char car;
    in >> N >> M;
    in.get();

    for( int i=1; i<=N; ++i )
    {
        for( int j=1; j<=N; ++j )
        {
            in >> a[i][j];
        }
        in.get();
    }

    for( int i=1; i<=M; ++i )
    {
        for( int j=1; j<=M; ++j )
        {
            in >> car;
            ++f[car-'a'+1];
        }
        in.get();
    }

    for( int i=M; i<=N; ++i )
    {
        for( int j=M; j<=N; ++j )
            d[i][j]=1;
    }

    for( int c=1; c<=26; ++c )
    {
        memset( s, 0, sizeof(s) );
        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]-'a'+1==c );
        }

        for(int i=M; i<=N; ++i)
        {
            for(int j=M; j<=N; ++j)
            {
               if( d[i][j] && s[i][j] - s[i-M][j] - s[i][j-M] + s[i-M][j-M]!=f[c] )
                    d[i][j]= 0;
            }
        }
    }
    for( int i=1; i<=N; ++i )
    {
        for( int j=1; j<=N; ++j )
        {
            nr+=d[i][j];
        }
    }
    out << nr;
    return 0;
}