Cod sursa(job #905279)

Utilizator cont_testeCont Teste cont_teste Data 5 martie 2013 18:30:37
Problema Matrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include<cstdio>
#include<cstring>

#define ALPHA 97
#define NMAX 1005



using namespace std;


int N,M,frec[30],result;
int DP[NMAX][NMAX];
char ch[NMAX][NMAX];
 int T[NMAX][NMAX];

void read ( void )
{

    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);

    scanf("%d%d",&N,&M);
    char buf;
	fscanf("%c",&buf);
    for(int i(1) ; i <= N; ++i && scanf("\n") )
        for(int ii(1) ; ii <= N ; ++ii )
           scanf(f,"%c",&ch[i][ii]);




	for(int i(1); i <= M ; ++i && scanf("\n") )

        for(int ii(1); ii <= M; ++ii )
    {
        scanf("%c",&buf);
        ++frec[buf-ALPHA+1];
    }

    fclose(stdin);

}

void solve ( void )
{
    //presupunem ca toate patrate N*N sunt bune
    for(int i(M); i<= N; ++i)
        for(int j(M) ; j<= N ;++j)
               DP[i][j]=1;

    //eliminam toate patrate care nu sunt bune
    for(int letter = 1 ; letter <= 26; ++letter)
    {
        memset(T,0,sizeof(T));
        for(int i(1); i <= N; ++i)
            for(int ii(1); ii <= N ; ++ii )
                T[i][ii]=T[i-1][ii] +T[i][ii-1]- T[i-1][ii-1]+(ch[i][ii]-ALPHA+1 == letter);


         for(int i(M); i <= N ; ++ i)
             for(int ii(M); ii <= N; ++ii )
                if(DP[i][ii] &&  T[i][ii] - T[i][ii-M] -T[i-M][ii] +T[i-M][ii-M] != frec[letter])
                    DP[i][ii] == 0;
    }

   //numaram cate pozitii au mai rams corecte
    for(int i(M); i <= N ; ++i)
        for(int ii(M); ii <=N ; ++ii)
        result + = ( DP[i][ii]==1 );



}
void write ( void )
{
  printf("%d\n",result);
  fclose(stdout);

}


int main ( void )
{
    read();
    solve();
    write();
    return 0;

}