Cod sursa(job #2565362)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 2 martie 2020 13:52:11
Problema Matrix Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f ( "matrix.in" );
ofstream g ( "matrix.out" );
int dp[1002][1002];
bool ok[1002][1002];
char s[1002];
int m1[1002][1002], ap[30];
int main()
{
    int n, m;
    f >> n >> m;

    for ( int i = 1; i <= n; i++ )
    {
        f >> s;

        for ( int j = 0; j < n; j++ )
            m1[i][j + 1] = s[j] - 'a';
    }

    for ( int i = 1; i <= m; i++ )
    {
        f >> s;

        for ( int j = 0; j < m; j++ )
        {
            int c = s[j] - 'a';
            ap[c]++;
        }
    }

    for ( int i = m; i <= n; i++ )
        for ( int j = m; j <= n; j++ )
            ok[i][j] = 1;

    for ( int c = 0; c < 27; c++ )
        if ( ap[c] != 0 )
        {
            for ( int i = 1; i <= n; i++ )
                for ( int j = 1; j <= n; j++ )
                {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + ( c == ( m1[i][j] - 'a' ) );

                    if ( i >= m && j >= m )
                    {
                        int nr = dp[i][j] - dp[i - m][j] - dp[i][j - m] + dp[i - m][j - m];

                        if ( nr != ap[c] )
                            ok[i][j] = 0;
                    }
                }
        }

    int rez = 0;

    for ( int i = 1; i <= n; i++ )
        for ( int j = 1; j <= n; j++ )
            if ( ok[i][j] )
                rez++;

    g << rez;
    return 0;
}