Cod sursa(job #3298027)

Utilizator EricDimiCismaru Eric-Dimitrie EricDimi Data 26 mai 2025 11:22:00
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MAX_DIM = 1'000;
const int SIGMA = 26;

bool ok[MAX_DIM + 1][MAX_DIM + 1];
char a[MAX_DIM + 1][MAX_DIM + 1];
int d[MAX_DIM + 1][MAX_DIM + 1];
int fr[SIGMA];
int n, m, c, cnt;
char ch;
/// ok[i][j] = 1, daca submatricea M x M cu coltul dreapta jos (i, j)
/// este o potrivire a lui A, sau 0 altfel

int main() {
    f >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            f >> a[i][j];
        
    for (int i = 1; i <= m; i++) 
        for (int j = 1; j <= m; j++) {
            f >> ch;
            fr[ch - 'a']++;
        }
    
    for (int i = m; i <= n; i++)
        for (int j = m; j <= n; j++)
            ok[i][j] = 1;
    
    for (int c = 0; c < SIGMA; c++) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                d[i][j] = ((a[i][j] - 'a') == c) + d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
        for (int i = m; i <= n; i++)
            for (int j = m; j <= n; j++)
                if (d[i][j] - d[i - m][j] - d[i][j - m] + d[i - m][j - m] != fr[c])
                    ok[i][j] = 0;
    }
    
    cnt = 0;
    for (int i = m; i <= n; i++)
        for (int j = m; j <= n; j++)
            cnt += ok[i][j];
    
    g << cnt << "\n";
    
    f.close();
    g.close();
    return 0;
}