Cod sursa(job #904920)

Utilizator cont_testeCont Teste cont_teste Data 4 martie 2013 23:49:58
Problema Matrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include<cstdio>
#include<cstring>

#define NMAX 1005

FILE *f=fopen("matrix.in","r");
FILE *g=fopen("matrix.out","w");

using namespace std;


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

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


    }
		fscanf(f,"%c",&buf);
	}

	for(int i(1); i <= M ; ++i )
	{
        for(int ii(1); ii <= M; ++ii )
    {
        fscanf(f,"%c",&buf);
        ++frec[buf-'a'];
    }
		fscanf(f,"%c",&buf);
	}

    fclose(f);

}

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-1][ii-1]-T[i][ii-1]+(ch[i][ii]-'a'+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;
    }


    for(int i(M); i <= N ; ++i)
        for(int ii(M); ii <=N ; ++ii)
        result+=(DP[i][ii]==1);



}
void write ( void )
{
  fprintf(g,"%d",result);
  fclose(g);

}


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

}