Cod sursa(job #3304861)

Utilizator Cyb3rBoltSbora Ioan-David Cyb3rBolt Data 28 iulie 2025 10:42:01
Problema Matrix Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("matrix.in");
ofstream fout("matrix.out");
int n, m;

struct Iris {
    int v[30] = {0};

    Iris operator + (const Iris &p) {
        Iris rez;
        for(int i=0; i<26; i++) rez.v[i] = v[i] + p.v[i];
        return rez;
    }
    Iris operator - (const Iris &p) {
        Iris rez;
        for(int i=0; i<26; i++) rez.v[i] = v[i] - p.v[i];
        return rez;
    }
    bool operator == (const Iris &p) {
        for(int i=0; i<26; i++)
            if(v[i] != p.v[i]) return false;
        return true;
    }
}sp[1003][1003], virus;

inline Iris getSum(int x1, int y1, int x2, int y2) { return sp[x2][y2] - sp[x1 - 1][y2] - sp[x2][y1 - 1] + sp[x1 - 1][y1 - 1]; }

int main()
{
    fin >> n >> m;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            char ch; fin >> ch;
            sp[i][j] = sp[i - 1][j] + sp[i][j - 1] - sp[i - 1][j - 1];
            sp[i][j].v[ch - 'a']++;
        }
    }
    for(int i=1; i<=m; i++) {
        for(int j=1; j<=m; j++) {
            char ch; fin >> ch;
            virus.v[ch - 'a']++;
        }
    }
    int rez = 0;
    for(int i=1; i+m-1<=n; i++)
        for(int j=1; j+m-1<=n; j++)
            if(getSum(i, j, i + m - 1, j + m - 1) == virus) rez++;
    fout << rez;

    return 0;
}