Cod sursa(job #2335850)

Utilizator iandavidroIan David Bocioaca iandavidro Data 4 februarie 2019 16:10:55
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <bits/stdc++.h>
#define N 1005

using namespace std;

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

int ok[N][N] , dp[N][N] ;
char mat[N][N] , a[N][N] ;
int n , m ;
int frec[35] ;

int main()
{
    int i , j , sol = 0 ;
    fin >> n >> m ;
    for ( i = 1 ; i <= n ; i++ )
        for ( j = 1 ; j <= n ; j++ )
            fin >> mat[i][j] ;

    for ( i = 1 ; i <= m ; i++ )
    {
        for ( j = 1 ; j <= m ; j++ )
        {
            fin >> a[i][j] ;
            frec[a[i][j]-'a'+1]++ ;
        }
    }
    for ( i = m ; i <= n ; i++ )
        for ( j = m ; j <= n ; j++ )
            ok[i][j] = 1 ;
    for (int ch = 1 ; ch <= 26 ; ch++ )
    {
        for ( i = 1 ; i <= n ; i++ )
            for ( j = 1 ; j <= n ; j++ )
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + (mat[i][j]-'a' + 1 == ch ) ;
        for ( i = m ; i <= n ; i++ )
            for ( j = m ; j <= n ; j++ )
                if ( dp[i][j] - dp[i-m][j] - dp[i][j-m] + dp[i-m][j-m] != frec[ch] )
                    ok[i][j] = 0 ;
    }
    for ( i = m ; i <= n ; i++ )
        for ( j = m ; j <= n ; j++ )
            sol = sol + ok[i][j] ;
    fout << sol ;
}