Cod sursa(job #2573558)

Utilizator marius004scarlat marius marius004 Data 5 martie 2020 18:08:39
Problema Matrix Scor 0
Compilator cpp-64 Status done
Runda recapitulare_finala Marime 1.22 kb
#include <fstream>

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

const int NMAX = 1005;
int n,m,genom[NMAX][NMAX],virus[256],s[NMAX][NMAX];
bool infectat[NMAX][NMAX];
char c;

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;
    
    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 >> c;
            virus[c]++;
        }
    }
    
    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 + m - 1 <= n;++i)
            for(int j = 1;j + m - 1 <= n;++j)
                if(suma(i,j,i + m - 1,j + m - 1) != virus[litera])
                    infectat[i][j] = false;
    }
    
    int sol = 0;
    for(int i = 1;i + m - 1 <= n;++i)
        for(int j = 1;j + m - 1 <= n;++j)
            sol += infectat[i][j];
    
    g << sol;
    
    return 0;
}