Cod sursa(job #301273)

Utilizator DraStiKDragos Oprica DraStiK Data 8 aprilie 2009 08:20:08
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <stdio.h>
#define DIM 1005
int v[DIM][DIM],s[DIM][DIM],st[DIM][DIM],x[30];
char c[DIM];
int n,m,nrt;
void read ()
{
    int i,j;
    scanf ("%d%d\n",&n,&m);
    for (i=1; i<=n; ++i)
    {
        gets (c);
        for (j=0; j<n; ++j)
			v[i][j+1]=c[j]-'a';
	}
	for (i=1; i<=m; ++i)
	{
		gets (c);
		for (j=0; j<m; ++j)
			++x[c[j]-'a'];
    } 
    nrt=(n-m+1)*(n-m+1);
}
int check (int i,int j,int m)
{
    if (j>=m)
        return s[i][j]-s[i-m][j]-s[i][j-m]+s[i-m][j-m];
    else
        return s[i][j]-s[i-m][j];
}
void solve ()
{
    int i,j,k;
    for (k=0; k<26; ++k)
    {
        for (i=1; i<=n; ++i)
            for (j=1; j<=n; ++j)
                if (v[i][j]==k)
                    s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+1;
                else
                    s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        for (i=m; i<=n; ++i)
            for (j=m; j<=n; ++j)
                if (!st[i][j] && check (i,j,m)!=x[k])
                {
					st[i][j]=1;
                    --nrt;
                }
    }
    printf ("%d",nrt);
}
int main ()
{
    freopen ("matrix.in","r",stdin);
    freopen ("matrix.out","w",stdout);
    read ();
    solve ();
    return 0;
}