Cod sursa(job #3236384)

Utilizator prares06Papacioc Rares-Ioan prares06 Data 28 iunie 2024 13:20:30
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<bits/stdc++.h>

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

int n, m, cnt, ap[26], dp[1005][1005];
char A[1005][1005];
bool valid[1005][1005];

int main(){
    fin >> n >> m;

    for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= n; ++j){
        fin >> A[i][j];
        valid[i][j] = true;
    }

    for(int i = 1; i <= m; ++i)
    for(int j = 1; j <= m; ++j){
        char c;
        fin >> c;
        ++ap[c - 'a'];
    }

    for(int k = 0; k < 26; ++k){
        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] + ((A[i][j] - 'a') == k);
        for(int i = m; i <= n; ++i)
            for(int j = m; j <= n; ++j)
                if(dp[i][j] - dp[i - m][j] - dp[i][j - m] + dp[i - m][j - m] != ap[k])
                    valid[i][j] = false;
    }

    for(int i = m; i <= n; ++i)
        for(int j = m; j <= n; ++j)
            cnt += valid[i][j];

    fout << cnt;
}