Cod sursa(job #843916)

Utilizator enedumitruene dumitru enedumitru Data 28 decembrie 2012 16:35:52
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
/*  Intai se calculeaza frecventa fiecarei litere in matricea virus de dimensiune N*N.
    Vom verifica pentru toate cele (M-N)*(M-N) matrici posibile daca sunt sau nu permutari ale matricii-virus.
    Pentru fiecare litera a alfabetului, construim matricea B ale carei elemente Bi,j = numarul de aparitii pe pozitii (x, y) cu 1 ≤ x ≤ i si 1 ≤ y ≤ j ale literei cautate.
    Relatia de recurenta este Bi,j = Bi-1,j+Bi,j-1-Bi-1,j-1, la care se adauga 1 daca si numai daca pe pozitia (i, j) se afla litera pe care o cautam.
    In aceste conditii, numarul de aparitii ale literei curente in submatricea cu colturile in (i-N+1, j-N+1) si (i, j) este Bi,j-Bi-N,j-Bi,j-N+Bi-N,j-N .
    Pe langa matricea B (in care se efectueaza preprocesarea pentru litera curenta) mai folosim matricea W in care tinem minte daca pentru o anumita pozitie
    s-a gasit vreo litera pentru care numarul de aparitii nu coincide cu cel dorit.
*/
#include<fstream>
using namespace std;
ifstream f("matrix.in");  ofstream g("matrix.out");
const int dim=1002;
int n, m, i, j, x, y, total, nrapar;
int  A[dim][dim], B[dim][dim], Nr[30];
bool W[dim][dim];
char ch;
int main ()
{   f>>m>>n;
    for(i=1; i<=m; ++i)
        for(j=1; j<=m; ++j)
            f>>ch, A[i][j]=ch-'a'+1;
    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j)
            f>>ch, Nr[ch-'a'+1]++;
    for(i=1; i<=26; ++i)
    {   for(x=1; x<=m; ++x)
            for(y=1; y<=m; ++y)
                B[x][y]=0;
        for(x=1; x<=m; ++x)
            for(y=1; y<=m; ++y)
            {
                if(i==A[x][y]) ++B[x][y];
                B[x][y]+=-B[x-1][y-1]+B[x-1][y]+B[x][y-1];
            }
        for(x=n; x<=m; ++x)
            for(y=n; y<=m; ++y)
            {
                nrapar=B[x][y]-B[x-n][y]+B[x-n][y-n]-B[x][y-n];
                if(nrapar!=Nr[i]) W[x][y]=true;
            }
    }
    for(i=n;i<=m;++i)
        for(j=n;j<=m;++j)
            if(!W[i][j]) ++total;
    g<<total<<"\n";
    return 0;
}