Cod sursa(job #3236805)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 1 iulie 2024 20:14:01
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <cstring>
#define ll long long

using namespace std;

ifstream cin("matrix.in");
ofstream cout("matrix.out");

const int NMAX = 1000;
const int CMAX = 26;

int n, m, answer;
int f[CMAX];
char a[NMAX + 1][NMAX + 1];
bool good[NMAX + 1][NMAX + 1];
int sp[NMAX + 1][NMAX + 1];

int 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() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= m; j++) {
            char x;
            cin >> x;
            f[x - 'a']++;
        }
    }

    for(int i = m; i <= n; i++) {
        for(int j = m; j <= n; j++) {
            good[i][j] = 1;
        }
    }

    for(int x = 0; x < CMAX; x++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                sp[i][j] = sp[i - 1][j] + sp[i][j - 1] - sp[i - 1][j - 1] + (a[i][j] - 'a' == x);
            }
        }

        for(int i = m; i <= n; i++) {
            for(int j = m; j <= n; j++) {
                good[i][j] &= (GetSum(i - m + 1, j - m + 1, i, j) == f[x]);
            }
        }
    }

    for(int i = m; i <= n; i++) {
        for(int j = m; j <= n; j++) {
            answer += good[i][j];
        }
    }
    cout << answer << '\n';

    return 0;
}