Cod sursa(job #2554974)

Utilizator marius004scarlat marius marius004 Data 23 februarie 2020 16:03:18
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <iostream>
#include <fstream>

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

const int NMAX = 1005;
char genom[NMAX][NMAX],virus[NMAX][NMAX];
int n,m,s[NMAX][NMAX],fr[30],sol;
bool infectat[NMAX][NMAX];

// infectat[i][j] - daca submatricea care incepe din (i,j) e infectata

int suma(int is,int js,int ij,int jj){
    return s[ij][jj] - s[is - 1][jj] - s[ij][js - 1] + s[is - 1][js - 1];
}

int main(){

    f >> n >> m;

    /// fr[litera] - de cate ori apare litera lit in virus
    /// infectat[i][j] daca submatricea care incepe din i,j este infectata
    /// pentru fiecare submatrice de (m * m) verific daca este infectata
    /// ca sa evitam folosirea de multa memeorie putem folosi un tablou unidimensional pe care facem o suma partiala
    /// pentru fiecare litera de la a la z verificam de cate ori apare litera lit in submatrice
    /// daca nu apare de acelasi numar de ori cu virusul atunci submatricea nu este infectata

    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= n;++j){
            f >> genom[i][j];
            infectat[i][j] = true;
        }
    }

    for(int i = 1;i <= m;++i){
        for(int j = 1;j <= m;++j){
            f >> virus[i][j];
            fr[ virus[i][j] - 'a']++;
        }
    }

    for(char litera = 'a';litera <= 'z';++litera){

        for(int i = 1;i <= n;++i)
            for(int j = 1;j <= n;++j)
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + (genom[i][j] == litera);

        for(int i = 1;i <= n - m + 1;++i){
            for(int j = 1;j <= n - m + 1;++j){

                int is = i,js = j,ij = i + m - 1,jj = j + m - 1;

                if(suma(is,js,ij,jj) != fr[litera - 'a'])
                    infectat[i][j] = false;
            }
        }
    }

    for(int i = 1;i <= n - m + 1;++i)
        for(int j = 1;j <= n - m + 1;++j)
            sol += infectat[i][j];

    g << sol;

    return 0;
}