Cod sursa(job #2547726)

Utilizator marius004scarlat marius marius004 Data 15 februarie 2020 17:03:11
Problema Matrix Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <iostream>
#include <fstream>

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

const int NMAX = 1005;
const int LITERE = 300;
char genom[NMAX][NMAX],virus[NMAX][NMAX];
int n,m,s[NMAX][NMAX][LITERE],fr[LITERE],sol;

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

int main(){
    
    f >> n >> m;
    
    for(int i = 1;i <= n;++i)
        for(int j = 1;j <= n;++j)
            f >> genom[i][j];
    
    for(int i = 1;i <= m;++i){
        for(int j = 1;j <= m;++j){
            f >> virus[i][j];
            fr[virus[i][j]]++;
        }
    }
    
    //fac sume partiale pentru fiecare litera de la 'a' la 'z'
    for(char litera = 'a';litera <= 'z';++litera){
        for(int i = 1;i <= n;++i)
            for(int j = 1;j <= n;++j)
                s[i][j][litera] = s[i - 1][j][litera] + s[i][j - 1][litera] -
                                   s[i - 1][j - 1][litera] + (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;
            
            bool ok = true;
            for(char litera = 'a';litera <= 'z' && ok;++litera)
                if(suma(is,js,ij,jj,litera) != fr[litera])
                    ok = false;
            
            sol += ok;
        }
    }
    
    g << sol;
    
    return 0;
}