Cod sursa(job #773963)

Utilizator vendettaSalajan Razvan vendetta Data 3 august 2012 02:24:25
Problema Matrix Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.75 kb
#include <iostream>
#include <fstream>

using namespace std;

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

#define nmax 1000
#define Litmax 26

int n, m, mat[nmax][nmax], viz[Litmax], frec_virus[Litmax];
int dp[nmax][nmax][Litmax], a[nmax][Litmax], b[Litmax];

void citeste(){

	f >> m >> n;//dim hartii genoului; dim hartii 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]-'a';
    }
    for(int i=1; i<=n; i++){
        string s;
        getline(f,s);
        for(int j=0; j<s.size(); j++) frec_virus[s[j]-'a']++;
    }
}

void rezolva(){

    //o aparitie in genom e daca gasesc un dreptunghi de aceelasi dimensiuni si cu aceleasi litere(nu conteaza ordinea in care apar)
    //pp ca coltul dreapta jos unui dreptunghi e in (i,j)

    int rez = 0;
    //dp[i][j][k] = numarul de aparitii a literei k in dreptunghiul cu coltul dreapta jos in (i,j) si coltul stanga sus in (1,1)
    //dp[i][j][k] = cati de k sunt pe coloana j deasupra linie i  + cati de j sunt pe linia in stanga coloanei j + /
    // cati de j sunt pana in dreptunghiul cu coltul dreapta jos in (i-1,j-1) si stanga sus in (1,1)

    //a[j][k] = numarul de aparitii a literei k pana pe linia i si acestia sa fie doar pe coloana j
    //b[k] = numarul de aparitii a literei k pana pe coloana j si acestia sa fie doar pe linia i

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

            for(int k='a'-'a'; k<='z'-'a'; k++)a[0][k] = 0;

            for(int k='a'-'a'; k<='z'-'a'; k++){
                int X = 0;//daca apare si pe pozitia i,j cresc nr de aparitii
                if (k == mat[i][j]) X = 1;

                dp[i][j][k] = a[j][k] + b[k] + dp[i-1][j-1][k] + X;
                a[j][k] = a[j][k] + X;
                b[k] += X;
            }
        }
        for(int k='a'-'a'; k<='z'-'a'; k++) b[k] = 0;
    }

    //acum aflu pentru fiecare litera decate ori apare in dreptunghiul 1,1; i,j folosind sume partiale

    for(int i=n; i<=m; i++){
        for(int j=n; j<=m; j++){
            for(int k=0; k<=26; k++) viz[k] = 0;
            for(int k='a'-'a'; k<='z'-'a'; k++){
                viz[k] = dp[i][j][k] - dp[i-n][j][k] - dp[i][j-n][k] + dp[i-n][j-n][k];
            }
            int ok = 1;
            for(int k=0; k<=26; k++)
                if (viz[k] != frec_virus[k]) ok =0;
            if (ok == 1) ++rez;
        }
    }

    g << rez << "\n";

}

void memorie(){

    int cat = 0;

    cat += sizeof(mat) + sizeof(viz) + sizeof(frec_virus) + sizeof(dp) + sizeof(a) + sizeof(b);
    cout << cat / 1024 << "\n";
}

int main(){

    citeste();
    rezolva();
    //memorie();

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

    return 0;

}