Cod sursa(job #3277127)

Utilizator jumaracosminJumara Cosmin-Mihai jumaracosmin Data 15 februarie 2025 12:34:41
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <bits/stdc++.h>

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

const int SIZE = 1005;
const int SIGMA = 'z' + 5;

int n, m;
char a[SIZE][SIZE], b[SIZE][SIZE];

// dp[i][j] este folosit pt sume partiale de frecvente de caractere
int dp[SIZE][SIZE];
bool ok[SIZE][SIZE];
int fr[SIGMA];
// ok[i][j] = 1, daca submatricea cu coltul din dreapta jos (i, j) este o "anagrama" a lui B


int64_t max(std::vector<int64_t> v){ return *std::max_element(v.begin(), v.end()); }

int64_t min(std::vector<int64_t> v){ return *std::min_element(v.begin(), v.end()); }

int main() 
{
    fin >> n >> m;
    // prima matrice
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            fin >> a[i][j];
    // a doua matrice, cea de cautat       
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= m; ++j)
            fin >> b[i][j];
    
    // frecventa pe matricea B
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= m; ++j)
            fr[b[i][j]]++;

    // daca facem sume partiale de frecventa pt fiecare litera (a...z), atunci pt ca o submatrice cu coltul
    // de jos in (i, j) sa respecte conditia, ea trebuie sa aiba frecventa buna pt fiecare caracter
    //presupunem ca toate submatricele sunt bune si verificam care nu sunt corecte
    memset(ok, true, sizeof(ok));
    for(char k = 'a'; k <= 'z'; ++k)
    {
        // sume partiale
        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] == k);

        // verificam frecventa pt fiecare candidat la solutie
        for(int i = m; i <= n; ++i)
            for(int j = m; j <= n; ++j)
            {
                int frecv = dp[i][j] - dp[i - m][j] - dp[i][j - m] + dp[i - m][j - m];
                if(frecv != fr[k])
                    ok[i][j] = 0;
            }
    }

    // daca ok[i][j] = 1, atunci avem o submatrice buna
    int ans = 0;
    for(int i = m; i <= n; ++i)
        for(int j = m; j <= n; ++j)
            ans += ok[i][j];

    fout << ans;

    return 0;
}