Cod sursa(job #774090)

Utilizator vendettaSalajan Razvan vendetta Data 3 august 2012 14:07:59
Problema Matrix Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <iostream>
#include <fstream>

using namespace std;

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

#define nmax 1005
#define Sigma 27

int mat[nmax][nmax], n, m, frec_virus[Sigma+'a'], dp[nmax][nmax];
bool in_regula[nmax][nmax];

void citeste(){

    f >> m >> n;//dimen genomului; dimen virusului
    f.get();
    for(int i=1; i<=m; i++){
        string s;
        getline(f,s);
        for(int j=0; j<s.size(); j++) mat[i][j+1] = s[j];
    }

    for(int i=1; i<=n; i++){
        string s;
        getline(f,s);
        for(int j=0; j<s.size(); j++) frec_virus[++s[j]];
    }

}

void nr_aparitii(int k){

    //nr de aparitii a literi k pana pe pozitia (i,j)

    for(int i=1; i<=m; i++) for(int j=1; j<=m; j++) dp[i][j]=0;

    for(int i=1; i<=m; i++){
        for(int j=1; j<=m; j++){
            dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1];
            if (k == mat[i][j]) ++dp[i][j];
        }
    }

}

void check(int k){

    //fac o matrice in_regula[i][j] = care imi zice daca dreptunghiul cu coltul dreapta jos in (i,j) are aceelasi litere ca si virusul(nu conteaza ordinea)

    for(int i=n; i<=m; i++){
        for(int j=n; j<=m; j++){
            int X = dp[i][j] - dp[i-n][j] - dp[i][j-n] + dp[i-n][j-n];
            if (X != frec_virus[k]) in_regula[i][j] = 0;
            else if (X == frec_virus[k]) in_regula[i][j] = 1;
        }
    }

}

void rezolva(){

    //fac acum numarul de a aparitii a literei a,b,c

    for(int k='a'; k<='z'; k++){
        nr_aparitii(k);
        check(k);
    }

    int rez = 0;

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

    //cout << rez << "\n";
    g << rez << "\n";

}

void memorie(){

    int sum = 0;
    sum = sizeof(in_regula)+ sizeof(dp)+sizeof(mat)+sizeof(frec_virus);

    cout << sum/1024 << "\n";

}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;

}