Cod sursa(job #773960)

Utilizator vendettaSalajan Razvan vendetta Data 3 august 2012 01:33:29
Problema Matrix Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <iostream>
#include <fstream>

using namespace std;

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

#define nmax 1005

int n, m, a[nmax][nmax], viz[200], frec_virus[200];

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++) a[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 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;
    for(int i=n; i<=m; i++){
        for(int j=n; j<=m; j++){
            //verific dreptunghiul cu coltul dreapta jos;
            for(int k='a'; k<='z'; k++) viz[k] = 0;
            for(int w=i; w>=i-n+1; w--){
                for(int k=j; k>=j-n+1; k--){
                    ++viz[a[w][k]];
                }
            }
            int ok = 1;
            for(int k='a'; k<='z'; k++) if (frec_virus[k] != viz[k]) ok =0;
            if (ok == 1) ++rez;
        }
    }

    g << rez << "\n";

}

int main(){

    citeste();
    rezolva();

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

    return 0;

}