Cod sursa(job #2516089)

Utilizator vlad082002Ciocoiu Vlad vlad082002 Data 30 decembrie 2019 12:38:52
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>
#include <set>
using namespace std;

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

int m, n, aparitii[1024][1024], virus[26];
char om[1024][1024];
bool notOk[1024][1024];

void citire() {
    fin >> m>> n;
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= m; j++)
            fin >> om[i][j];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) {
            char x;
            fin >> x;
            virus[x-'a']++;
        }
}

void solve() {
    for(int c = 0; c < 26; c++) {
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= m; j++) {
                if(om[i][j]-'a' == c)
                    aparitii[i][j] = 1;
                else
                    aparitii[i][j] = 0;
                aparitii[i][j] += aparitii[i-1][j] + aparitii[i][j-1] - aparitii[i-1][j-1];
            }
        for(int i = 1; i+n-1 <= m; i++)
            for(int j = 1; j+n-1 <= m; j++)
                if(aparitii[i+n-1][j+n-1] - aparitii[i-1][j+n-1] - aparitii[i+n-1][j-1] + aparitii[i-1][j-1] != virus[c])
                    notOk[i][j] = true;
    }

    int res = 0;
    for(int i = 1; i+n-1 <= m; i++)
        for(int j = 1; j+n-1 <= m; j++)
            res += !notOk[i][j];
    fout << res;
}

int main() {
    citire();
    solve();
}